백준 | 9655번. 돌 게임

9655번. 돌 게임

• 이 문제는 DP를 활용하는 문제이다.

문제

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

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

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

입력

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

출력

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

문제 풀이

이 문제에서는 상근이와 창영이가 턴을 번갈아가면서 돌을 가져가며, 돌은 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");
        }
    }
}