[BOJ] 2482번: 색상환

2482번: 색상환

풀이

원으로 계산하면 골치가 아파서 선형으로 만들어서 계산하고 나중에 원으로 만들어서 계산하면 된다.

조건 범위 내 모든 n에서 k=0일 땐 1이고(아무 것도 고르지 않는 것도 경우로 취급), k=1일 땐 n이다.

 

n>1의 경우, n번째 색을 고르거나 안 고르는 두 가지 경우로 생각할 수 있는데 

n번째 색을 고르면 n - 2개 중 k - 1개를 고른 것과 같고,

n번째 색을 고르지 않으면 n - 1개 중 k를 고른 것과 같다.

 

다시 원으로 합칠 때는 양쪽 끝을 합친다고 생각하면 되기 때문에 선형의 양쪽 끝이 같은 경우를 생각해 줘야 한다.

양 끝에 색이 칠해져 있다면 이 경우는 불가능하므로 그걸 피하기 위해 양쪽 끝 중 하나를 잡아서 계산한다. 

 

아까와 동일하게 n번째 색을 고르거나 안 고르는 두 가지 경우로 생각할 수 있는데,

n번째 색을 고른 경우는 n - 3개 중 k - 1개를 고른 경우이고 

n번째 색을 고르지 않은 경우는 n - 1개 중 k개를 고른 경우이다.

모든 경우의 수를 구해야 하므로 n개 중 조건에 맞춰 k개를 고르는 경우의 수는 n번째 색을 고른 경우와 안 고른 경우를 합친 것이다.

코드

#include <cstdio>

const int div = 1000000003;
int dp[1001][1001];

int main()
{
    int N, K;
    scanf("%d %d", &N, &K);

    for (int i = 1; i <= N; ++i)
        dp[i][0] = 1;
    for (int i = 1; i <= N; ++i)
        dp[i][1] = i;
    for (int i = 2; i <= N; ++i)
    {
        for (int j = 2; j <= N; ++j)
        {
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % div;
        }
    }
    printf("%d\n", (dp[N - 3][K - 1] + dp[N - 1][K]) % div);

    return 0;
}