문제 소개
두 명이 번갈아 진행하는 구슬 게임을 생각해 봅시다. 게임에는 총 n개의 구슬이 있으며, 각 라운드마다 플레이어는 반드시 양의 정수인 제곱수(1, 4, 9, 16 ...)만큼의 구슬을 가져가야 합니다. 만약 자기 차례에 가져갈 수 있는 제곱수가 없다면 그 플레이어가 패배합니다.
주어진 숫자 n에 대해, 우리가 항상 먼저 시작하고 매번 최적의 선택을 한다고 가정할 때 이 게임에서 승리할 수 있는지를 판별하는 것이 목표입니다.
예제로 이해하기
예를 들어 입력값이 14라면 결과는 True(승리)입니다. 과정은 다음과 같습니다.
- 첫 차례에 우리는 9개(3²)의 구슬을 가져가고, 상대에게는 5개가 남습니다.
- 상대는 최대 4개(2²)까지 가져갈 수 있으므로 4개를 가져가면 1개가 남습니다.
- 다음 차례에 우리는 마지막 1개(1²)를 가져가고, 남은 구슬이 0개가 되어 상대는 더 이상 움직일 수 없습니다.
- 따라서 우리가 승리합니다.
해결 접근 방식
이 문제는 재귀적 탐색(게임 이론의 필승/필패 상태 분석)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- n ≤ 0이면 현재 차례인 플레이어가 질 수밖에 없으므로 False를 반환합니다.
- 현재 상태에서 가져갈 수 있는 모든 제곱수 i²에 대해, 상대에게 (n − i²)개의 구슬을 남겼을 때 상대가 지는 경우(not solve(n − i²))가 하나라도 존재하면 우리가 이길 수 있습니다.
- 가능한 선택 중 하나라도 승리로 이어지면 True를 반환하고 탐색을 종료합니다.
구체적인 알고리즘 단계는 다음과 같습니다.
- n ≤ 0이면 False를 반환합니다.
- ans := False로 초기화합니다.
- i를 √n의 정수 부분부터 1까지 감소시키며 반복합니다.
- i * i > n이면 반복문을 빠져나갑니다.
- ans := ans OR (not solve(n − i * i))로 갱신합니다.
- ans가 True가 되면 즉시 ans를 반환합니다.
- 반복이 끝나면 ans를 반환합니다.
Python 구현 코드
from math import sqrt
def solve(n):
if n <= 0:
return False
ans = False
for i in range(int(sqrt(n)), 0, -1):
if i * i > n:
break
ans = ans | (not solve(n - i * i))
if ans:
return ans
return ans
print(solve(14))실행 결과
입력:
14
출력:
True
마무리 정리
이 풀이는 각 상태에서 가능한 모든 제곱수 선택을 재귀적으로 시도해 보고, 상대방을 필패 상태로 몰아넣을 수 있는 선택이 존재하는지를 확인합니다. 첫 번째 승리 경로를 찾으면 조기 반환(early return)하여 불필요한 탐색을 줄입니다. 다만 이 코드는 단순 재귀 방식이라 입력값이 커지면 시간이 오래 걸릴 수 있으며, 실전에서는 메모이제이션(memoization)을 적용해 중복 계산을 제거하면 성능을 크게 향상시킬 수 있습니다.