[백준 9655번] 돌 게임 Java 풀이

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. 문제

2. 입력

3. 출력

4. 예제

5. 풀이

이번 문제는 DP로 문제를 풀어도 되며 게임을 생각해 보면 DP가 아닌 그냥 간단하게 문제가 풀립니다.

 

문제 풀이 전 문제에 대한 이해가 필요한 부분이 있습니다.

 

문제에서 말한 완벽하게 게임을 했을 때는 본이이 이기기 위한 경우를 말하는 것 입니다.

 

즉 돌이 3개 이상 남은 경우 3개를 가져가는 것을 말하는 것입니다.

 

● 간단한 문제 풀이

 

게임에서 돌을 가지고 갈 수 있는 수는 1개와 3개로 모두 홀수개입니다.

 

즉 3개를 들고 가는 것과 1개를 3번 들고 가는 것이 같은 결과를 만드는 것입니다.

 

돌이 3개가 있을 때 상근이 3개를 모두 가져가 이기는 것과,

 

상근이 1개 창영이 1개 다시 상근이 1개를 가져가 이기는 것 결과는 똑같은 것입니다.

 

그럼 게임 룰이 가지고 갈 수 있는 돌이 1개인 경우와 1개, 3개인 경우가 같은 것이 됩니다.

 

그럼 1개씩 가지고 가서 게임의 승자를 찾는 것은 결국 돌이 짝수개 인지 홀수개 인지 확인하면 되는 것입니다.

 

● DP를 이용한 문제 풀이

 

DP를 이용해 문제를 푸는 경우는 먼저 가지고 갈 수 있는 돌의 수가 1개 또는 3개입니다.

 

돌을 3개를 가지고 가기 위해서는 주어진 돌이 3개 이상인 경우 가능합니다.

 

그럼 돌이 1개인 경우는 1개를 상근이 가지고가 상근이 승리하게 됩니다.

 

돌이 2개인 경우는 1개를 상근이 가지고 가고 나머지 1개를 창영이 들고 가 창영이 승리합니다.

 

돌이 3개인 경우는 3개를 상근이 가지고가 상근이 승리하게 됩니다.

 

돌이 4개 이상인 경우 DP[N] = DP[N-1] 승자의 반대가 됩니다.

 

N개의 돌 중 1개를 뺀 N-1개의 돌에서 완벽한 게임을해서 이긴 승리자가 DP에 저장되어 있고 1개의 돌이 남아 한 번의 턴이 더 남은 것이므로 승리자가 반대가 됩니다.

6. 코드

전체 코드는 Git에 있습니다.

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

if((Integer.parseInt(br.readLine()) & 1) == 1)
	bw.write("SK\n");
else
	bw.write("CY\n");
bw.flush();

BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

int rockCnt = Integer.parseInt(br.readLine());

boolean[] dp = new boolean[rockCnt+1];

if(rockCnt>1)
	dp[2] = true;

for(int i=4; i<=rockCnt; i++){
	dp[i] = !dp[i-1];
}

if(dp[rockCnt])
	bw.write("CY\n");
else
	bw.write("SK\n");
bw.flush();