[BOJ] 백준 9661번 : 돌 게임 7 (JAVA)

문제

돌 게임은 두 명이서 즐기는 재밌는 게임이다.

 

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 4x개 만큼 가져갈 수 있다. 즉, 가능한 개수는 1, 4, 16, 64, ...개 이다. 4x개만큼 돌을 가져갈 수 있는 방법이 없는 사람이 게임을 지게 된다.

 

두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

 

 

입력

첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1,000,000,000,000)

 

 

출력

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

 

 

풀이

간단한 게임 이론 문제였습니다.

 

이 문제도 "9657번 돌 게임 3" 처럼 현재와 다음 상황을 정의하는 방식을 사용할 것입니다.

위 방식을 잘 모르신다면 아래 포스팅을 참고하시길 바랍니다.

 

 

[BOJ] 백준 9657번 : 돌 게임 3 (JAVA)

 

 

우선, 규칙성을 찾기 위해서 boolean[] 타입의 dp를 정의해 줍시다.

 

N = 0 일 때는 돌을 가져갈 수 없으므로 dp[0] = false 입니다.

그리고 이 다음 과정부터는 아래 반복문을 돌립니다.

 

 

 

 

돌을 가져갈 수 있는 개수는 4의 n제곱 꼴이고, n은 0부터 시작하므로 상근이가 특정 돌 n개를 가져가고 난 다음 상황에 대한 정의는 dp[i - 4 ^ cnt] 로 표현할 수 있습니다.

 

그리고 다음 상황(창영이 차례) 에서 dp[i - 4 ^ cnt] = false인, 즉 단 한 번이라도 창영이가 지는 상황이 나온다면, 현재 상황(상근이 차례) 에서 무조건 이기는 상황이 존재합니다.

 

반대로, 다음 상황에서 창영이가 모두 이긴다면, 현재 상황은 패배하는 상황 밖에 없습니다.

위 반복문을 적당히 돌리고 나면 아래와 같은 규칙성을 보입니다.

 

 

idx	0	1	2	3	4
dp[idx]	false	true	false	true	true

 

 

바로, N을 5로 나눈 나머지가 0과 2일 때만, 상근이가 패배하고 나머지는 전부 승리한다는 점이죠.

 

위 규칙을 찾았으면, 바로 소스코드로 작성하면 됩니다.

아래 소스코드를 참고하시길 바랍니다.

 

 

소스코드

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.