문제 개요
Amal과 Bimal 두 플레이어가 돌 게임을 진행하며, Amal이 먼저 시작합니다. 처음에는 더미에 n개의 돌이 놓여 있습니다. 각 플레이어는 자신의 차례에 더미에서 0이 아닌 제곱수(1, 4, 9, 16, ...) 개만큼 돌을 가져가야 합니다. 더 이상 가져갈 돌이 없어 움직일 수 없게 된 플레이어가 패배합니다. 따라서 n이 주어졌을 때, 선공인 Amal이 이 게임에서 승리할 수 있는지 확인해야 합니다.
예를 들어 입력이 n = 21이라면 결과는 True입니다. Amal이 먼저 16개를 가져가고, Bimal이 4개를 가져간 뒤, Amal이 마지막 1개를 가져가 승리하기 때문입니다.
해결 접근 방식
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다. dp[k]는 'k개의 돌이 남아 있을 때 현재 차례인 플레이어가 승리할 수 있는가'를 의미하며, 자신의 수 이후 상대방이 패배 상태(dp 값이 False)가 되도록 만들 수 있다면 현재 플레이어는 승리합니다. 풀이 과정은 다음과 같습니다.
- n 이하의 모든 제곱수를 squares 리스트에 저장합니다. 연속된 제곱수의 차이는 홀수(1, 3, 5, 7, ...)이므로 square와 increase 변수를 이용해 효율적으로 생성할 수 있습니다.
- dp 배열을 크기 (n + 1)로 생성하고 dp[0] := False로 설정합니다. 돌이 하나도 남아 있지 않으면 현재 플레이어는 패배하기 때문입니다.
- k를 1부터 n까지 순회하면서 각 제곱수 squares[s]를 빼본 뒤, 남은 돌의 상태 dp[k - squares[s]]가 패배 상태(False)라면 dp[k] := True로 설정합니다.
- 모든 반복이 끝나면 dp[n], 즉 dp의 마지막 요소를 반환합니다.
예시 구현
아래 파이썬 코드를 통해 더 잘 이해할 수 있습니다.
def solve(n):
squares = []
square = 1
increase = 3
while square <= n:
squares.append(square)
square += increase
increase += 2
squares.append(square)
dp = [None] * (n + 1)
dp[0] = False
for k in range(1, n + 1):
s = 0
dp[k] = False
while squares[s] <= k and not dp[k]:
if not dp[k - squares[s]]:
dp[k] = True
s += 1
return dp[-1]
n = 21
print(solve(n))입력
21
출력
True
이 알고리즘의 시간 복잡도는 대략 O(n√n)입니다. 각 상태 k에 대해 최대 √k개의 제곱수만 검사하면 되기 때문입니다. 따라서 n이 수천 정도의 크기라면 충분히 빠르게 답을 구할 수 있습니다.