[BOJ] 백준 9658번 : 돌 게임 4 (JAVA)

문제

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

 

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

 

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

 

 

입력

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

 

 

출력

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

 

 

풀이

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

 

특히, "9657번 돌 게임 3"와 상당히 유사하고 전반적인 로직도 이와 동일하기때문에, 이 문제를 아직 풀어보지 않으신 분들은 아래 포스팅을 참고하시길 바랍니다.

 

 

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

 

 

위 포스팅에서 언급했듯이, 이번에도 현재 상황과 다음 상황을 정의하면서 현재 상황이 지는지 이기는지 판단하는 것이 중요했습니다.

 

현재 상황에서 돌을 n개 빼냈을 때, 창영이가 모두 승리하는 상황이라면, 상근이는 패배하고, 반대로 창영이가 지는 상황이 단 하나라도 있으면, 상근이가 승리합니다.

 

위 로직을 이용하여 dp 값을 나열하면 아래와 같은 규칙성을 보입니다.

 

 

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

 

 

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

 

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

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

 

 

소스코드

 

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