[BOJ] 2482. 색상환 (🥇, DP)

🔗

📝

원형 형태의 DP 문제이다. N의 수를 늘려가면서 n번째 칸을 선택하거나, 선택하지 않는 경우의 수로 나눠서 생각하면 된다. N=4, K=2 라고 가정할 때, 아래와 같이 생각해볼 수 있다.

먼저 N=4 번째 칸을 선택하지 않은 경우이다. 이 경우는 사실상 4칸 중 1칸은 무조건 제외한 나머지 3칸 중에 2칸을 고르는 경우인데, 원형 3칸에서 2칸을 고르는 경우의 수는 0이 된다. 그래서 현재 상황에서는 0이지만 어쨌거나 4칸 중 2칸을 고르는 경우의 수에 3칸 중 2칸에서만 고르는 경우의 수가 포함되는 것이다.

다음은 N=4 번째 칸을 선택하는 경우이다. 이 경우는 무조건 옆에 한 칸을 떨어트려 놓고 생각해야 한다. 결국 선택한 건 1칸이지만 옆의 떨어트릴 한 칸까지 포함해서 2칸을 빼놓고 골라야 하는 것이다. 그리고 선택된 1칸이 있기 때문에 나머지 2칸 중에서 1칸만 고르면 된다. 그래서 2칸 중 1칸을 고르는 경우의 수 역시 4칸 중 2칸을 고르는 경우의 수에 포함된다.

4칸 중 2칸 고르기 = 3칸 중 2칸 고르기 + 2칸 중 1칸 고르기

점화식으로 나타내면 아래와 같다.

이 문제는 애초에 시작을 4칸 부터 시작해야 별다른 예외상황 처리 없이 한 번에 계산된다. 3칸에서 2칸을 고르는 경우가 자동으로 0으로 초기화되기 때문에 모든 상황을 자연스럽게 원형으로 고려하게 되기 때문이다.

참고로 K 가 N/2 보다 큰 경우는 아예 불가능하므로 바로 0을 출력한다.

import java.util.*;
import java.io.*;

public class Main {
    static int MOD = 1_000_000_003;

    static int sol(int N, int K) {

        if (N / 2 < K) {
            return 0;
        }

        int[][] dp = new int[N + 1][K + 1];

        for (int i = 1; i <= N; i++) {
            dp[i][1] = i;
        }

        for (int i = 4; i <= N; i++) {
            for (int j = 2; j <= K; j++) {
                dp[i][j] = (dp[i-1][j] + dp[i-2][j-1]) % MOD;
            }
        }

        return dp[N][K];
    }
    
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();

        System.out.println(sol(N, K));
    }
}