BOJ 2482 색상환

색상환

(http://boj.kr/2482)

먼저, 원형이 아닌 선형일 때의 경우의 수를 찾는다. 선형인 경우는 k가 0일 때 1, k가 1일 때 n이 된다.

그리고, k가 1보다 클 때는 n번째 색을 고르는 경우와 안 고르는 경우로 나눌 수 있는데,

n번째 색을 고르면, 색이 n-2개일 때 k-1개를 고른 경우이고,

n번째 색을 고르지 않으면, 색이 n-1개일 때 k개를 고른 경우이다.

둘을 합치면 색이 n개일 때 k개를 고른 경우를 알 수 있다.

그리고 이 것을 원형으로 바꾸기 위해서는, 선형의 색의 양 끝을 잇는다고 생각할 수 있다.

이을 때 양 끝이 모두 칠해져 있으면 불가능한 경우이므로, 이 경우를 피하기 위해서 끝의 색 중 하나를 정한다고 생각한다.

그리고, 이 색을 고르는 경우와 고르지 않는 경우로 나눌 수 있다.

고르는 경우는, 고른 색의 양 옆은 고르지 않아야 하므로 n-3개에서 k-1개를 고른 경우이다.

고르지 않은 경우는, n-1개에서 k개를 고른 경우이다.

#include <bits/stdc++.h>
 
const int r = 1000000003;
 
int d[1004][1004];
 
int main() {
    int n, k;
 
    scanf("%d %d", &n, &k);
 
    for (int i = 1;i <= n;++i)
        d[i][0] = 1;
    for (int i = 1;i <= n;++i)
        d[i][1] = d[i - 1][1] + 1;
    for (int i = 2;i < n;++i)
        for (int j = 2;j <= k;++j)
            d[i][j] = (d[i - 1][j] + d[i - 2][j - 1]) % r;
 
    printf("%d", (d[n - 1][k] + d[n - 3][k - 1]) % r);
 
    return 0;
}