문제

https://www.acmicpc.net/problem/9655
돌 게임은 두 명이서 즐기는 재밌는 게임이다.
탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.
두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.

입력

첫째 줄에 노트북의 세로와 가로 길이를 나타내는 N(1 ≤ N ≤ 40)과 M(1 첫째 줄에 N이 주어진다. (1 ≤ N ≤ 1000)

출력

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

풀이

선공 후공 턴제 형식으로 진행되는 게임의 승부를 일단 예시를 들어보면서 분석해본다.

• n=1: 선공자가 1개 가져가서, 선공 승
• n=2: 선공자가 1개 가져간 후 후공자가 나머지 1개 가져가서 후공 승
• n=3: 선공자가 3개 가져가서, 선공 승
• n=4: 선공자가 1개 또는 3개 가져간 후 후공자가 나머지 3개 또는 1개 가져가서 후공 승
• n=5: 선공자가 1개 가져한 후 후공자가 3개 또는 1개 가져간 다음 나머지 1개 또는 3개 가져가서 선공 승
  …

이런 식으로 게임 진행을 분석하다보면 먼저 보이는 건 n이 홀수일 때 선공인 상근이가 이기고, n이 짝수일 때 후공인 창영이가 이긴다는 규칙이 보일 것이다. 그러니까… 이 문제가 홀짝문제로 보일 수는 있다…

홀짝으로 해결은 할 수는 있지만, 다른 관점으로 문제를 생각해본다.
문제에서 1개 또는 3개씩 돌을 가져간다 했으니 이를 무더기로 놓고 생각을 해본다. 그리고 둘 다 완벽하게 게임을 한다 했으니, 바로 무더기로 돌을 가져갈 수 있다 한다. 즉, n개일 때, 1또는 3인 무더기로 나눌 수 있는 최소 무더기 수를 dp[n]이라 설정한다.
그렇다면 돌이 1개 또는 3개일 때 1무더기가 있는 것이고, 2개일 때는 1인 무더기가 2개가 있는 것이다. 이를 배열로 표현하자면, dp[1] = 1, dp[2] = 2, dp[3] = 1 이다.
그리고 4개 이상부터는 1인 무더기 1개와 3으로 이루어진 무더기 수 또는 3인 무더기 1개와 1로 이루어진 무더기 수 중 최소 무더기 수가 될 것이고, 5 또한 마찬가지로 최소 무더기 수를 설정하다보면 dp[n]은 이렇게 나올 수 있다.

dp[n] = min(dp[n-1] + 1, dp[n-3] + 1) (n >= 4)

n개의 최소 무더기는 n-3개의 최소 무더기 수 + 1 또는 n-1개의 최소 무더기 수 + 1 중 최소값이다. 이를 구현하면 다음과 같다.

private static void sol1(int n) {
    // 1,3으로 무더기 만들 수 있는 최소 무더기 수
    int[] dp = new int[1001];

    dp[1] = 1; // 1
    dp[2] = 2; // 1, 1
    dp[3] = 1; // 3

    // 4이상 부터 1,3으로 된 무더기 중 최소 몇 무더기가 나올 것인가?
    for(int i = 4; i <= n; i++){
        int catch1Case = 1 + dp[i - 1];
        int catch3Case = 1 + dp[i - 3];
        dp[i] = Math.min(catch1Case, catch3Case);
    }

    System.out.println(dp[n] % 2 == 1 ? "SK" : "CY");
}

결론

문제를 풀다보면 규칙이 보일 것이다. 이는 찾기 쉬운 규칙이었을 것이다. 하지만 규칙이 안 보인다면, 직접 적어보면서 찾아야 한다. 이는 작은 문제를 찾아가면서 푸는 방법이며 다이나믹 프로그래밍 기법 중 한 방법이다.
작은 문제들을 풀면서 큰 문제들로 넓혀가는 것을 의미한다. 실제로 1일때, 2일때, 3일때, 4이후 일때 등등 도출하면서 작은 문제들을 해결하고, 그것들을 활용하여 N일때 이렇게 된다라는 규칙을 프로그래밍 할 수 있다.