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

문제

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

 

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

 

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

 

 

입력

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

 

 

출력

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

 

 

풀이

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

 

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

 

N = 0 부터 나열해 봅시다.

돌을 못 가져가므로 false 입니다.

 

N = 1일 때, 돌을 1개 가져갈 수 있으므로 true 입니다.

 

N = 2일 때, 돌을 1개 가져갈 수 있습니다. 하지만, 창영이가 다음 턴에서 남은 돌을 1개 가져가므로 false 입니다.

 

N = 3일 때, 돌을 3개 가져갈 수 있으므로 true 입니다.

 

N = 4 일 때, 돌을 1개 또는 3개 가져가도 다음 턴에 창영이가 돌을 3개 또는 1개 가져가므로 false 입니다.

 

위 과정을 반복해보면 아시겠지만, N이 홀수일 때는 상근이가 이기고, N이 짝수일 때는 창영이가 이깁니다.

이러한 규칙성을 그대로 소스코드로 옮기시면 됩니다.

 

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

 

참고

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

 

 

9659번: 돌 게임 5

 

 

소스코드

 

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