정점이 n개인 다각형이 있다고 가정해 보겠습니다. 이 다각형에는 n개의 뒤집기 축(flipping axis)과 n개의 회전점이 존재하며, 뒤집기 축과 회전점은 다음과 같은 성질을 가집니다.
- n이 홀수라면, 각 뒤집기 축은 하나의 정점과 반대편 변의 중점을 지난합니다.
- n이 짝수라면, 절반의 축은 마주 보는 한 쌍의 정점을 지나고, 나머지 절반의 축은 마주 보는 한 쌍의 변을 지난합니다.
- 인접한 두 축 사이의 각도는 360/2n도입니다.
이제 주어진 다각형에 회전 연산을 적용해 보겠습니다. 다각형에는 서로 다른 n가지 종류의 회전자(rotator)가 있으며, k-회전자는 다각형을 k번 축을 기준으로 시계 방향으로 (360 × k)/n도만큼 회전시킵니다.
입력 리스트(input_list)에는 여러 개의 정수 쌍(pair)이 들어 있습니다. 각 쌍의 첫 번째 정수는 다각형을 회전할지 뒤집을지를 결정하는데, 1이면 회전, 2이면 뒤집기를 의미합니다. 두 번째 정수는 k 값으로, 뒤집기 연산이라면 k번 축을 기준으로 뒤집고, 회전 연산이라면 그 각도만큼 회전하게 됩니다. 이러한 회전과 뒤집기는 리스트가 빌 때까지 순서대로 수행됩니다.
따라서 우리의 과제는 리스트에 연산을 하나 추가하여 다각형을 초기 위치로 되돌리는 것입니다.
위 그림은 두 종류의 다각형에 대한 회전축을 보여줍니다.
예를 들어 입력이 n = 6, input_list = [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]이라면 출력은 (1, 4)가 됩니다. 즉, 주어진 변환들을 모두 수행한 뒤 4번째 축을 기준으로 회전하면 다각형이 초기 위치로 재설정됩니다.
해결 접근 방법
이 문제는 누적 위치(position)와 뒤집기 여부(decision_var)를 추적하는 방식으로 해결할 수 있습니다. 단계별로 살펴보면 다음과 같습니다.
- decision_var := False, position := 0으로 초기화합니다.
- input_list의 각 항목에 대해 다음을 수행합니다.
- x := item[0], y := item[1]
- x가 1이면(회전), position := position + y
- 그렇지 않으면(뒤집기), position := y − position 으로 갱신하고 decision_var를 반전(not)시킵니다.
- 모든 연산이 끝난 뒤 position := position mod n을 적용합니다.
- decision_var가 참이라면 (2, position)을 반환합니다.
- 그렇지 않다면 (1, n − position)을 반환합니다.
예제 코드
아래 파이썬 구현을 통해 더 잘 이해해 보겠습니다.
def solve(n, input_list):
decision_var = False
position = 0
for item in input_list:
x = item[0]
y = item[1]
if x == 1:
position += y
else:
position = y - position
decision_var = not decision_var
position = position % n
if decision_var:
return (2, position)
else:
return (1, n - position)
print(solve(6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]))
입력
6, [[1, 2], [1, 4], [2, 3], [2, 5], [1, 6]]
출력
(1, 4)
이처럼 회전은 누적 덧셈으로, 뒤집기는 현재 위치를 기준으로 반사시키는 방식으로 처리한 뒤, 최종적으로 n으로 나눈 나머지와 뒤집기 여부만 판단하면 다각형을 초기 상태로 되돌리는 데 필요한 단 하나의 연산을 효율적으로 구할 수 있습니다.