문제 소개
서로 다른 높이를 가진 n개의 탑을 담은 배열 height가 있다고 가정해 보겠습니다. 아말(Amal)과 비말(Bimal) 두 사람이 이 탑들을 가지고 게임을 진행하며, 규칙은 다음과 같습니다.
- 아말이 항상 먼저 시작합니다.
- 매 턴마다 현재 플레이어는 높이가 X인 탑 하나를 선택해, 각각 높이가 Z인 Y개의 탑으로 분해합니다. (단, Y × Z = X이고 X > 1, Y > 1)
- 더 이상 분해할 수 있는 탑이 남아 있지 않아 움직일 수 없게 된 플레이어가 패배합니다.
우리가 할 일은 이 게임의 승자 이름을 구하는 것입니다.
예시로 이해하기
입력이 height = [3, 1, 2]라고 가정해 봅시다. 초기 탑의 높이는 {3, 1, 2}입니다.
- 아말이 높이 2짜리 탑을 높이 1짜리 탑 두 개로 나누면, 새로운 높이 배열은 {3, 1, 1, 1}이 됩니다.
- 비말은 높이 3짜리 탑을 높이 1짜리 탑 세 개로 나눌 수 있습니다.
- 이제 모든 탑의 높이가 1이므로 아말은 더 이상 움직일 수 없고, 비말이 승리합니다.
접근 방법: 스프라그-그런디 정리
이 문제는 독립적인 여러 게임 상황이 동시에 진행되는 전형적인 조합 게임(combinatorial game)입니다. 따라서 스프라그-그런디(Sprague-Grundy) 정리를 적용하면 효율적으로 해결할 수 있습니다.
핵심 아이디어는 다음과 같습니다.
- 각 탑의 높이에 대해 그런디 값(Grundy number)을 미리 계산해 둡니다.
- 모든 탑의 그런디 값을 XOR한 결과가 0이 아니면 선공(아말)이, 0이면 후공(비말)이 승리합니다.
- 탑을 분해할 때는 홀수인 약수 쌍(Y 또는 Z 중 하나가 홀수인 경우)만 고려하면 됩니다. 짝수 개로 나누면 대칭 전략 때문에 그런디 값이 상쇄되기 때문입니다.
알고리즘 단계
그런디 값 테이블을 생성하는 util() 함수를 정의합니다. 초기 한계값(limit)은 10³ + 5로 설정합니다.
result: 크기가 limit이고 0으로 채워진 배열을 생성합니다.- i를 2부터 limit − 1까지 반복하면서:
- s := 새로운 집합(set)을 만듭니다.
- j를 1부터 √i의 내림값까지 반복하면서:
- d := i ÷ j의 몫, r := i ÷ j의 나머지
- r이 0이면(j가 i의 약수이면):
- j가 홀수이면 result[d]를 s에 추가
- d가 홀수이면 result[j]를 s에 추가
- j := 0부터 시작해 s에 속하지 않는 가장 작은 수를 찾아 result[i]에 저장합니다(mex 연산).
- 완성된 result 배열을 반환합니다.
메인 로직에서는 다음을 수행합니다.
- g := util()로 그런디 값 테이블을 준비합니다.
- r := 0으로 초기화한 뒤, height의 각 원소 i에 대해 r := r XOR g[i]를 계산합니다.
- r이 0이 아니면 "Amal", 0이면 "Bimal"을 반환합니다.
구현 코드
def util(limit=10**3+5):
result = [0] * limit
for i in range(2, limit):
s = set()
for j in range(1, int(i**0.5) + 1):
d, r = divmod(i, j)
# j가 i의 약수인 경우
if r == 0:
if j & 1: # j가 홀수이면
s.add(result[d])
if d & 1: # d가 홀수이면
s.add(result[j])
# mex: 집합에 없는 가장 작은 음이 아닌 정수
j = 0
while j in s:
j += 1
result[i] = j
return result
g = util()
def solve(height):
r = 0
for h in height:
r ^= g[h]
if r:
return "Amal"
else:
return "Bimal"
height = [3, 1, 2]
print(solve(height))입력
[3,1,2]
출력
Bimal
마무리
이처럼 그런디 수를 사전 계산해 두면 각 게임 상태를 O(1)로 조회할 수 있고, 전체 승패도 단순한 XOR 누적만으로 빠르게 판별할 수 있습니다. 시간 복잡도는 테이블 생성에 약 O(limit·√limit), 질의 처리에는 O(n)으로 매우 효율적이므로, 유사한 조합 게임 문제에 널리 활용할 수 있는 강력한 패턴입니다.