[Baekjoon] 9657번: 돌 게임 3

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

9657번: 돌 게임 3

문제 설명

돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며 돌은 1개, 3개 또는 4개를 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이긴다. 두 사람이 완벽하게 게임했을 때 이기는 사람을 구하는 프로그램을 작성해라. 게임은 상근이가 먼저 시작한다.

입력

1 <= N <= 1000

출력

상근이가 이기면 SK를, 창용이가 이기면 CY를 출력한다.

풀이 방법

먼저 작은 수로 게임을 시뮬레이션해보자. 기억할 점은 항상 상근이가 먼저 시작하고 둘 다 완벽하게 게임을 한다는 것이다. 앞으로 상근이는 S, 창용이는 C라고 하겠다.

1. 돌이 1개면 S가 1개를 가져가서 S가 이긴다.
2. 돌이 2개면 S가 1개 -> C가 1개를 가져가서 C가 이긴다.
3. 돌이 3개면 S가 3개를 가져가서 S가 이긴다.
4. 돌이 4개면 S가 4개를 가져가서 S가 이긴다.
5. 돌이 5개면 S가 3개 -> C가 1개 -> S가 1개를 가져가서 S가 이긴다.
6. 돌이 6개면 S가 4개 -> C가 1개 -> S가 1개를 가져가서 S가 이긴다.
7. 돌이 7개면 S가 1개 -> C가 4개 -> S가 1개 -> C가 1개를 가져가서 C가 이긴다.
8. 돌이 8개면 S가 1개 -> C가 1개 -> S가 4개 -> C가 1개 -> S가 1개를 가져가서 S가 이긴다.
9. 돌이 9개면 S가 3개 -> C가 1개 -> S가 3개 -> C가 1개 -> S가 1개를 가져가서 S가 이긴다.
10. 돌이 10개면 S가 3개 -> C가 1개 -> S가 4개 -> C가 1개 -> S가 1개를 가져가서 S가 이긴다.

보면 돌이 1개, 3개, 4개, 5개인 경우 상근이가 이기고 돌이 2개인 경우에만 창용이가 이기는 구조가 반복된다. 이를 어떻게 코드로 구현할까? 두 가지 방법이 있는데 하나는 mod 연산을 활용하는 방법이고 또 다른 하나는 DP를 활용하는 방법이다.

1. MOD 연산 활용

MOD 연산은 나머지를 구하는 연산이다. 위 결과를 보면 2, 7이 창용이가 이기는 걸 볼 수 있다. 이후에도 계산해보면 12, 17, 22, ... 로 나올 것이다. 이는 MOD 5 연산 시 결과값이 항상 2가 나온다는 것을 알 수 있다. 따라서 다음과 같이 코드를 작성할 수 있다.

System.out.print(n % 5 == 2 ? "CY" : "SK");

규칙을 찾아 매우 간단하게 해결할 수 있다.

2. DP 활용

좀 더 복잡한 방법으로 DP를 활용할 수 있다. 먼저 코드를 보자.

import java.io.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int[] dp = new int[1001];
        
        dp[1] = 1;
        dp[2] = 0;
        dp[3] = 1;
        dp[4] = 1;
        
        int n = Integer.parseInt(br.readLine());
        
        for (int i = 5; i <=n; i++) {
            if (dp[i - 1] == 0) {
                dp[i] = 1;
            }
            if (dp[i - 3] == 0) {
                dp[i] = 1;
            }
            if (dp[i - 4] == 0) {
                dp[i] = 1;
            }
        }
        
        System.out.print(dp[n] == 1 ? "SK" : "CY");
    }
}

먼저 돌을 가져가는 경우는 1개, 3개, 4개이다. 두 사람은 항상 최선의 방법으로 게임을 완벽하게 하기 때문에 자신이 이길 수 있는 경우의 수가 한 가지라도 있다면 그 방법으로 이긴다. 생각할 것은 상근이가 항상 먼저 놓는다는 것이다. DP에는 마지막으로 가져간 사람을 넣어 놓는다. dp[i - 1]의 의미는 돌을 1개 가져가기 전에 마지막으로 가져간 사람을 구하는 것이다. 즉, 돌을 1개 가져가기 전에 가져간 사람이 창용이라면 상근이가 마지막으로 1개를 가져가면 게임이 끝난다. 따라서 돌을 1개, 3개, 4개 가져가기 전에 창용이가 가져갈 경우를 찾는다. 한 번이라도 창용이가 가져가는 경우가 있으면 상근이가 무조건 이기게 된다.