[백준] 9655번 : 돌 게임 – JAVA [자바]

 

https://www.acmicpc.net/problem/9655

9655번: 돌 게임

 

 

 

---

 

• 문제

 

 

---

• 문제 풀이

백준 9655번 돌 게임은 DP (다이나믹 프로그래밍)를 이용해서 푸는 문제이다. DP에 대해서 조금 더 알고 싶으면 밑에 있는 링크를 참고해 주면 되겠다.

 

https://propercoding.tistory.com/entry/알고리즘-다이나믹-프로그래밍-Dynamic-Programming

[알고리즘] 다이나믹 프로그래밍 (Dynamic Programming)

이 문제에서는 상근이와 창영이가 턴을 번갈아가면서 돌을 가져가며, 돌은 1개나 3개를 가져갈 수 있다. 그리고 마지막 돌을 가져가는 사람이 게임을 이기게 되고 돌 n개가 있을 때 누가 이기는 지를 구하면 되는 실버 5 난이도의 DP 문제이다.

 

예를 한번 보겠다.

n = 1 : 돌이 1개가 있으면 상근이가 1개를 가져가면 끝나므로 상근이가 이긴다.

n = 2 : 처음에 상근이가 1개를 가져가고 창영이가 남은 1개를 가져가면 되므로 창영이가 이긴다.

n = 3 : 상근이가 처음에 돌 3개를 가져가면 끝나므로 상근이가 이긴다.

n = 4 : 상근이가 돌 1개를 가져가든, 3개를 가져가든 돌이 1개나 3개가 남으므로 창영이가 이긴다.

n = 5 : 상근이가 처음에 돌 1개를 가져갈 수 도 있고 3개를 가져갈 수도 있다. 

→ 1개를 가져갔을 경우 : 4개가 남고 창영이가 1개를 가져가든 3개를 가져가든 1개나 3개가 남으므로 상근이가 이긴다. 

→ 3개를 가져갔을 경우 : 2개가 남고 창영이가 1개만 가져갈 수 있으므로 상근이가 이긴다.

 

이 문제는 1차원 int형 배열로 풀 수 있다. 이 예시들로 본 것처럼 돌을 1개를 가져가는 경우, 그리고 3개를 가져가는 경우 둘 다 고려해야 한다. 

dp[n] = Math.min(dp[n-1], dp[n-3]) + 1;

 

Math.min 함수를 사용한 이유는 문제에 나온 것처럼 상근이와 창영이가 게임을 완벽하게 하기 때문에 최솟값을 구해야 한다. 그리고 dp [n]이 홀수면 상근이가 이기는 게임이고 dp [n]이 짝수면 창영이가 이긴다.

 

 

---

• 코드

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] dp = new int[1001];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 1;
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.min(dp[i-1],dp[i-3]) + 1;
        }
        if (dp[n] % 2 == 0) {
            System.out.print("CY");
        } else {
            System.out.print("SK");
        }
    }
}

 

 

---

• 후기

그렇게 어렵지 않은 실버 5 난이도의 DP 문제였다.