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

문제

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

 

탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개, 3개 또는 4개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.

 

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

 

 

입력

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

 

 

출력

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

 

 

풀이

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

 

상근이가 지는 경우를 false, 이기는 경우를 true로 표시하겠습니다.

 

N = 0 부터 나열해 봅시다. 그리고 boolean[] 타입의 dp를 정의하겠습니다.

 

N = 0 일 때, 상근이가 돌을 못 가져가므로 dp[0] = false 입니다.

 

N = 1일 때, 상근이가 돌을 1개 가져가면, 창영이 입장에서 dp[0] = false 로 지게 됩니다.

따라서 dp[1] = true 입니다.

 

N = 2일 때, 상근이가 돌을 1개 가져가면, 창영이 입장에서 dp[1] = true 로 이기게 됩니다.

따라서 dp[2] = false 입니다.

 

N = 3일 때, 상근이가 돌을 1개 또는 3개 가져갈 수 있습니다.

만약, 상근이가 돌을 1개 가져간다면, 창영이 입장에서 dp[2] = false 로 지게 됩니다. 상근이가 돌을 3개 가져가도, 창영이 입장에서 dp[0] = false 로 지게 됩니다.

따라서 dp[3] = true 입니다.

 

상근이가 돌 n개를 가져갔을 때, 창영이가 지는 경우가 단 하나라도 있으면, 현재 상태는 무조건 이기는 상황인 점을 유의하시길 바랍니다.

반대로, 상근이가 돌 n개를 가져갔을 때, 창영이가 모두 이기는 상황이라면, 현재 상태는 무조건 지는 상황입니다.

 

위와 같이 현재 상황에 대해서 다음 상황을 정의하다보면, dp 배열은 다음과 같은 규칙성을 보입니다.

 

 

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

 

 

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

 

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

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

 

 

참고

위 로직은 "9660번 돌 게임 6" 문제에 100% 적용이 가능합니다. 자료형을 long인 점만 유의하면 AC를 받으실 수 있습니다.

 

 

9660번: 돌 게임 6

 

 

소스코드

 

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