문제 개요
게임 쇼에 원형으로 배치된 2n개의 방이 있다고 가정해 보겠습니다. 이 중 한 곳에는 참가자가 찾아야 할 경품이 숨겨져 있습니다. 방들은 시계 방향으로 1, 2, 3, …, n, −n, −(n−1), …, −1 순서로 번호가 붙어 있습니다. 각 방에는 문이 하나씩 있으며, 이 문을 통해 다른 방으로 이동할 수 있습니다. 모든 문에는 x라는 표식이 적혀 있는데, 이는 현재 방에서 거리 x만큼 떨어진 방으로 연결된다는 뜻입니다. x가 양수이면 시계 방향으로 x번째 방을, x가 음수이면 반시계 방향으로 x번째 방을 가리킵니다.
우리가 구해야 할 것은, 경품이 그곳에 숨겨져 있을 경우 참가자가 결코 찾지 못하는 방, 즉 경품을 숨길 수 있는 방의 개수입니다.
예시
예를 들어 입력이 input_array = [[4, 2]]라고 해보겠습니다. 이때 출력은 [2]가 됩니다.
입력의 첫 번째 값 n은 전체 방 개수의 절반을, 두 번째 값은 참가자가 탐색을 시작하는 방 번호를 의미합니다. 이 예제에서는 2 × 4 = 8개의 방이 있으며, 참가자는 시계 방향으로 2번째 방에서 탐색을 시작합니다. 방은 시계 방향으로 1, 2, 3, 4, −4, −3, −2, −1 순서로 번호가 매겨져 있습니다.
참가자는 2 → −4 → −1 → 1 → 3 → −2 → −1 → 1 → 3 → −2 → … 순서로 방을 돌아다니게 됩니다. 즉, 4번 방과 −3번 방은 한 번도 방문되지 않습니다. 따라서 경품이 이 두 방 중 하나에 숨겨져 있다면 참가자는 절대 찾을 수 없으며, 정답은 2가 됩니다.
해결 절차
이 문제는 오일러 피(phi) 함수와 법(modulo) r에 대한 2의 곱셈 위수(multiplicative order)를 활용하면 효율적으로 풀 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 실제로 방문되는 방의 개수는 법 r에 대한 2의 위수와 같습니다. 여기서 r은 2n + 1을 시작 방 번호 q와의 최대공약수(gcd)로 약분한 값입니다.
- 따라서 정답은 2n − ordr(2)가 됩니다.
구체적인 절차는 다음과 같습니다.
- prime_num_find(n) : 에라토스테네스의 체 방식으로 n 이하의 모든 홀수 소수를 구해 리스트로 반환합니다.
- factor_finder(p) : 미리 구해 둔 소수 목록을 이용해 p를 소인수분해하고, {소인수: 지수} 형태의 딕셔너리를 반환합니다.
- euler_func(p) : 소인수분해 결과를 이용해 오일러 피 함수 값을 계산합니다. 즉, φ(p) = ∏ (value − 1) × value^(지수 − 1) 입니다.
- solve(input_array) : 각 질의 (p, q)에 대해 다음을 수행합니다.
- r = 2p + 1을 계산한 뒤, gcd(r, q mod r)로 나누어 기약 형태로 만듭니다.
- t_value = euler_func(r)을 구합니다.
- t_value의 각 소인수 value에 대해, t_value가 value로 나누어떨어지면서 2^(t_value ÷ value) mod r == 1을 만족하는 동안 t_value를 계속 나눕니다. 이 과정을 거치면 t_value가 법 r에 대한 2의 최소 위수가 됩니다.
- 정답인 2p − t_value를 결과 리스트에 추가합니다.
구현 예시
다음 구현을 통해 더 잘 이해할 수 있습니다.
import math
def prime_num_find(n):
p_nums = [2]
check = bytearray(n)
for value in range(3, n, 2):
if check[value]:
continue
p_nums.append(value)
for i in range(3 * value, n, 2 * value):
check[i] = 1
return p_nums
def factor_finder(p):
p_nums = prime_num_find(45000)
f_nums = {}
for value in p_nums:
if value * value > p:
break
while p % value == 0:
p //= value
f_nums[value] = f_nums.get(value, 0) + 1
if p > 1:
f_nums[p] = 1
return f_nums
def euler_func(p):
f_nums = factor_finder(p)
t_value = 1
for value in f_nums:
t_value *= (value - 1) * value ** (f_nums[value] - 1)
return t_value
def solve(input_array):
output = []
for item in input_array:
p, q = item[0], item[1]
r = 2 * p + 1
r //= math.gcd(r, q % r)
t_value = euler_func(r)
for value in factor_finder(t_value):
while t_value % value == 0 and pow(2, t_value // value, r) == 1:
t_value //= value
output.append(2 * p - t_value)
return output
print(solve([[4, 2]]))
입력
[[4, 2]]
출력
[2]
마무리
이 프로그램은 소수 판별, 소인수분해, 오일러 피 함수, 곱셈 위수 계산이라는 네 가지 수학적 도구를 조합하여, 모든 방을 일일이 시뮬레이션하지 않고도 참가자가 찾을 수 없는 방의 개수를 빠르게 계산합니다. 덕분에 방의 개수가 매우 커지더라도 효율적으로 동작한다는 장점이 있습니다.