[C/C++] 백준 #2482 색상환(동적 계획법)

색상환 문제는 중복조합 문제입니다.  중복조합 문제는 식만 잘 세우면, 조합으로 문제를 해결할 수 있습니다.

 

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

2482번: 색상환

색상환이 있습니다.  이 색상환은 비슷한 색들이 순차적으로 바뀌면서 쭉 이어지게 환(ring)을 이루게 됩니다.

 

color ring

색상환에 있는 모든 색은 이웃한 색과 비슷합니다.  그래서 이 색상환에서 몇개의 색을 고를때 이웃한 색을 고르지 않으려고 합니다.  고르는 경우의 수가 얼마가 되는지가 문제입니다.

 

환을 이루지 않는 경우에는 n개 중 k개를 고를 때 이웃하지 않은 경우의 수는 \(_{k+1}H_{n-2k+1}\)이 됩니다.

 

하지만 환을 이루는 경우에는 두가지를 생각해야 합니다.  색상환에 1부터 n까지 숫자를 붙인다면, n번째 색상환이 반드시 선택되는 경우의 수는 \(_{k}H_{n-2k}\)라고 할 수 있습니다.  다음은 n번째 색상환이 반드시 선택되지 않는 경우의 수입니다.  이 경우의 수는 \(_{k+1}H_{n-2k}\)이 됩니다.  이 두가지를 합치면 n개의 색상환에서 k의 색을 이웃하지 않게 선택할 수 있습니다.

 

중복조합은 다음과 같은 공식을 이용해서 조합으로 바꿀 수 있습니다.

\[ _nH_k = _{n+k-1}C_k \]

 

하지만, 저는 실제 프로그램 작성할 때에는 동적 계획법을 이용해서 풀었습니다.

색상환의 첫번째를 선택한 것과 아닌 것으로 나누어서 풀었습니다.  dp00는 첫번째가 선택되지 않고 마지막도 선택되지 않은 경우입니다.  dp01은 첫번째가 선택되지 않고 마지막은 선택된 것입니다.  dp10과 dp11은 첫번째가 선택되지 않은 경우입니다.

선택하지 않을 경우에는 마지막이 선택이 되었든 아니든 상관이 없으니 dp00+dp01이 되고, 선택된 총 개수는 늘어나지 않습니다.  선택할 경우에는 마지막에 선택이 안된 경우에 붙일 수밖에 없기 때문에 dp00값을 사용하고 선택된 총 개수를 하나 증가시킵니다.

 

첫번째가 선택된 경우에는 dp11 값을 마지막에 사용할 수 없습니다.  첫번째가 선택되지 않은 경우에는 dp00+dp01을 해서 결과를 내도록 합니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #2482 - Color Ring
//        - by Aubrey Choi
//        - created at 2019-07-23
//------------------------------------------------
#include <stdio.h>
#define    MOD    1000000003

//    H(k,n-2k)+H(k+1,n-2k)=C(n-k-1,k-1)+C(n-k,k)=2*C(n-k-1,k-1)+C(n-k-1,k)
int main()
{
    int n, k;
    scanf("%d%d", &n, &k);
    if(n < 2*k) { puts("0"); return 0; }

    static long long dp00[501], dp01[501], dp10[501], dp11[501];
    dp00[0] = 1, dp11[1] = 1;
    for(int i = 2; i <= n; i++)
    {
        dp00[0] = 1;
        for(int j = k; j >= 1; j--)
        {
            dp00[j] = (dp00[j] + dp01[j])%MOD;
            dp01[j] = dp00[j-1];
            dp10[j] = (dp10[j] + dp11[j])%MOD;
            dp11[j] = dp10[j-1];
        }
    }
    printf("%lld\n", (dp00[k]+dp01[k]+dp10[k])%MOD);
}