게임 규칙과 문제 정의
1부터 n까지의 자연수로 이루어진 집합 {1, 2, ..., n}이 있다고 가정해 보겠습니다. 아말(Amal)과 비말(Bimal) 두 사람이 이 집합으로 게임을 진행하며, 규칙은 다음과 같습니다.
아말이 항상 선공입니다.
각 차례마다 현재 플레이어는 집합에 남아 있는 수 중에서 소수 p를 하나 선택한 뒤, p와 p의 모든 배수를 집합에서 제거합니다.
더 이상 선택할 수 있는 소수가 없는 플레이어가 패배합니다. 따라서 n이 주어졌을 때 최종 승자의 이름을 구하는 것이 목표입니다.
예를 들어 입력이 n = 5라고 해보겠습니다. 초기 집합은 {1, 2, 3, 4, 5}입니다. 아말이 p = 2를 선택하면 2와 4가 함께 제거되어 집합은 {1, 3, 5}가 됩니다. 남은 소수는 3과 5 두 개뿐이므로 비말이 어느 쪽을 골라도 추가로 지워지는 수는 없습니다. 이후 아말이 마지막 소수를 제거하면 비말은 더 이상 둘 수 없으므로, 최종 출력은 Amal이 됩니다.
접근 방식: 소수 개수로 승패 판별하기
핵심 관찰은 다음과 같습니다. 한 번의 이동에서 선택된 소수 하나는 반드시 새롭게 제거되고, 게임은 집합에 소수가 하나도 남지 않을 때까지 계속됩니다. 즉, 전체 게임의 이동 횟수는 곧 n 이하의 소수 개수 π(n)과 같습니다. 두 플레이어가 번갈아 이동하므로 결과는 다음과 같이 결정됩니다.
- π(n)이 홀수이면 마지막 이동을 아말이 하게 되어 비말이 움직일 수 없으므로 Amal이 승리합니다.
- π(n)이 짝수이면 마지막 이동을 비말이 하게 되어 아말이 움직일 수 없으므로 Bimal이 승리합니다.
결국 문제는 "n 이하의 소수가 몇 개인가?"로 단순화됩니다. 이 값은 에라토스테네스의 체(Sieve of Eratosthenes)를 이용해 미리 전처리해 두면 각 질의를 O(1)에 답할 수 있습니다. 알고리즘 절차는 다음과 같습니다.
- 크기가 100000인 배열 primes와 sieve를 만들고 모든 값을 0으로 초기화합니다.
- i를 2부터 99999까지 순회합니다.
- sieve[i]가 0이면 i는 소수입니다. primes[i] = primes[i-1] + 1로 누적 소수 개수를 기록하고, i부터 시작해 i씩 증가하며 i의 모든 배수를 sieve로 표시합니다.
- 그렇지 않으면 i는 합성수이므로 primes[i] = primes[i-1]을 그대로 이어받습니다.
- 메인 로직에서는 primes[n]이 짝수면 "Bimal", 홀수면 "Amal"을 반환합니다.
구현 예제
다음 파이썬 코드로 직접 확인해 볼 수 있습니다.
primes = [0 for i in range(100001)]
sieve = [0 for i in range(100001)]
for i in range(2, 100000):
if sieve[i] == 0:
primes[i] = primes[i-1]+1
for j in range(i, 100001, i):
sieve[j] = i
else:
primes[i] = primes[i-1]
def solve(n):
return "Bimal" if primes[n] % 2 == 0 else "Amal"
n = 5
print(solve(n))
입력
5
출력
Amal
복잡도 분석
소수 개수를 미리 구하는 전처리 단계는 에라토스테네스의 체 특성상 O(N log log N)의 시간이 소요되며, 이후 임의의 n에 대해 승자를 판별하는 데는 O(1)이면 충분합니다. 공간 복잡도는 배열 두 개를 유지하므로 O(N)입니다. 덕분에 여러 개의 n 값에 대해 반복적으로 질의가 들어오는 상황에서도 매우 효율적으로 답변할 수 있습니다.