Implementation

문제 https://codeforces.com/problemset/problem/25/A 풀이 n 개의 원소를 가진 수열이 입력으로 들어오고 입력으로 들어온 숫자 중 홀/짝이 다른 하나의 숫자의 인덱스(1-base 인덱스)를 출력하면 된다. 수열이 들어올 때마다 홀/짝 각각의 마지막 인덱스를 저장하고, 홀수의 개수, 짝수의 개수를 세면된다. 마지막 이렇게 얻어진 개수로 홀/짝인지 판별을 한 뒤에, 홀수면 짝수의, 짝수면 홀수의 마지막 인덱스를 출력하면 된다. 코드 #include <iostream> int main() { int n; std::cin >> n; int oddCount = 0; int evenCount = 0; int oddIndex = 0; int evenIndex = 0; for (int i = 1; i <= n; ++i) { int number; std::cin >> number; if (number % 2 == 0) { evenCount++; evenIndex = i; } else { oddCount++; oddIndex = i; } } std::cout << (oddCount == 1 ? oddIndex : evenIndex) << std::endl; }

문제 https://school.programmers.co.kr/learn/courses/30/lessons/68646 풀이 문제의 조건은 쉬운데, 풀이 과정은 쉽지 않아보인다. 하지만 문제를 최대한 단순화해보자. 기본적으로, 인접한 두 풍선을 고를 수 있고 두 풍선중 번호가 더 큰 풍선을 터트려야 한다. 하지만 1회에 한정에서 번호가 더 작은 풍선을 터트릴 수 있다. 일단 기본적으로 마지막까지 남을 수 있는 풍선의 개수를 세야 하므로 모든 풍선에 대해 확인해봐야 한다. 그리고 마지막까지 남을 수 있는 풍선이라고 했으므로, 항상 마지막에 고르는 두 풍선들 중 하나는 현재 내가 확인하고 싶은 풍선일 것이다. ...

문제 https://www.acmicpc.net/problem/14891 풀이 상황 설명이 굉장히 난해하고 비직관적이므로 글을 잘 읽어야 한다. 문제를 겨우 이해하고 나면 알고리즘이나 구현 능력 자체는 크게 요구하지 않는다. 글을 이해하는것 자체가 이 문제의 가장 큰 난관이다. 이 문제에서 톱니바퀴는 현실의 톱니바퀴처럼 움직이지 않는다. 이전 톱니바퀴가 회전하면 다음 톱니바퀴도 회전해야할지 말아야 할지를 이미 돌아간 상태의 이전 톱니바퀴가 아닌 돌기 전의 이전 톱니바퀴의 상태로 판단해야 한다. 코드 class Gear(): def __init__(self, stat): self.__stat = stat self.__top = 0 self.__left = 6 self.__right = 2 def rotate(self, drct): self.__top = (self.__top - drct) % 8 self.__left = (self.__left - drct) % 8 self.__right = (self.__right - drct) % 8 @property def top(self): return self.__stat[self.__top] @property def left(self): return self.__stat[self.__left] @property def right(self): return self.__stat[self.__right] def left_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num - 1, 0, -1): if gears[next_gear].right != gears[cur_gear].left: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break def right_shift(gear_num, drct): new_drct = drct * -1 cur_gear = gear_num for next_gear in range(gear_num + 1, 5): if gears[next_gear].left != gears[cur_gear].right: rotate_queue.append((next_gear, new_drct)) cur_gear = next_gear new_drct *= -1 else: break gear1 = Gear(list(map(int, input()))) gear2 = Gear(list(map(int, input()))) gear3 = Gear(list(map(int, input()))) gear4 = Gear(list(map(int, input()))) gears = [None, gear1, gear2, gear3, gear4] k = int(input()) answer = 0 rotate_queue = [] for _ in range(k): num, drct = map(int, input().split()) rotate_queue.append((num, drct)) left_shift(num, drct) right_shift(num, drct) for g, d in rotate_queue: gears[g].rotate(d) rotate_queue = [] rank = 1 for idx in range(1, 5): answer += gears[idx].top * rank rank *= 2 print(answer)

문제 https://www.acmicpc.net/problem/14890 풀이 경사로의 방향을 생각해보면 왼쪽에서 오른쪽으로 올라가는 방향이 있을 것이고, 그 반대인 오른쪽에서 왼쪽으로 올라가는 방향도 있을 것이다. 이러한 경우에는 한 번에 해결하기 보다는 배열을 정방향, 역방향으로 각각 순회하여 경사로를 만들어주는 것이 좋다. 따라서 알고리즘은 다음과 같다. 주어진 2차원 배열을 Transpose한 배열을 하나 더 만든다. 세로 모양의 길을 찾기 위해서이다. 정방향으로 우선 순회한다. 다음에 있는 칸의 높이가 현재 칸보다 같으면 count를 하나 늘리고(count는 경사로를 지을 수 있는지 판단할 때 사용한다.) 1 낮으면 일단은 패스(역방향에서 확인한다), 1 높으면 경사로를 설치할 수 있는지 판단한다. 경사로를 설치할 수 있는지 판단하는 기준은 두 가지이다. 일단 경사로를 설치하기 충분한 공간이 확보되었는가 (count로 충분한 공간이 얼마나 있는지를 알 수 있다.), 만약 가능하다면 이미 그곳에 경사로가 설치되어 있지는 않는가(이는 is_built 배열로 추적한다. 하지만 정방향을 먼저 하므로 지금 상황에선 필요 없다.) 역방향으로 순회한다. 정방향과 같지만 정방향을 순회하면서 경사로를 지은 곳을 유의할 필요가 있다. 코드 def check(line): is_built = [False] * n current_height = line[0] count = 1 for idx in range(1, n): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): is_built[idx - back] = True count = 1 else: return False current_height = line[idx] else: return False current_height = line[n - 1] count = 1 for idx in range(n - 2, -1, -1): if current_height == line[idx]: count += 1 elif current_height - line[idx] == 1: current_height = line[idx] continue elif current_height - line[idx] == -1: if count >= l: for back in range(1, l + 1): if is_built[idx + back]: return False is_built[idx + back] = True count = 1 else: return False current_height = line[idx] else: return False return True n, l = map(int, input().split()) graph = [] graph_tranposed = [[0] * n for _ in range(n)] answer = 0 for _ in range(n): graph.append(list(map(int, input().split()))) for row in range(n): for column in range(n): graph_tranposed[row][column] = graph[column][row] for idx in range(n): answer += 1 if check(graph[idx]) else 0 answer += 1 if check(graph_tranposed[idx]) else 0 print(answer)

문제 https://www.acmicpc.net/problem/14499 풀이 특별한 알고리즘이나 문제 해결 기법을 사용할 필요 없이, 순수하게 딕셔너리 자료구조만을 사용해서 풀 수 있는 문제이다. 주어진 주사위의 전개도를 이용하여 각 면에 숫자를 붙이고(면에 써져있는 숫자가 아닌 각 면을 인식하게 해주는 숫자, 이하 ID숫자라고 하겠다.) 이를 방향: ID 숫자의 꼴로 딕셔너리를 생성한다. 또 ID숫자: 면에 적힌 숫자 꼴로 딕셔너리를 하나 더 생성하여 두개의 딕셔너리로 주사위의 방향과 각 면에 적혀있는 숫자를 추적할 수 있다. 코드 import copy def north(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["s", "n", "u", "e", "w", "l"]): dice_drct[new] = original_drct[ori] def south(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["n", "s", "l", "e", "w", "u"]): dice_drct[new] = original_drct[ori] def east(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["w", "e", "n", "u", "l", "s"]): dice_drct[new] = original_drct[ori] def west(): global dice_drct original_drct = copy.deepcopy(dice_drct) for new, ori in zip(["u", "l", "n", "e", "w", "s"], ["e", "w", "n", "l", "u", "s"]): dice_drct[new] = original_drct[ori] def change(): if graph[x][y] == 0: graph[x][y] = dice_num[dice_drct["l"]] else: dice_num[dice_drct["l"]] = graph[x][y] graph[x][y] = 0 def check(x, y): if x < 0 or x >= n or y < 0 or y >=m: return False return True n, m, x, y, k = map(int, input().split()) graph = [] for _ in range(n): graph.append(list(map(int, input().split()))) orders = list(input().split()) dice_num = {1: 0, 2: 0, 3: 0, 4: 0, 5: 0, 6: 0} dice_drct = {"u": 1, "l": 6, "n": 2, "e": 3, "w": 4, "s": 5} for order in orders: isTrue = False if order == "1": if check(x, y + 1): y += 1 east() change() isTrue = True if order == "2": if check(x, y - 1): y -= 1 west() change() isTrue = True if order == "3": if check(x - 1, y): x -= 1 north() change() isTrue = True if order == "4": if check(x + 1, y): x += 1 south() change() isTrue = True if isTrue: print(dice_num[dice_drct["u"]])