[고급-7] 동적테이블 응용2

색상환 : 미국의 화가 먼셀이 교육용으로 고안한 20색상환

문제 : n개의 색에서 인접하지 않은 k개의 색을 구할 때, 경우의 수를 10억3으로 나눈 값을 출력하라!

solve(a, b) = 현재 a번 색상에 대해 고려하는 상태, 규칙에 맞도록 b개의 색깔을 이미 선택한 상태.

하지만 문제 발생!

따라서 f(a,b,c)는 c가 참이면 마지막 색을 고를 수 없는 상태.

f함수 설계:

if(b==k) return 1; ==> 찾으면 리턴1

if(a>=n-can) return 0; ==> a가 2단계로 건너뛰는 경우도 있기 때문에

return (f(a+1,b,can)+f(a+2,b+1,can)) %MOD; ==> 두가지 상태의 합을 MOD로 나눈 값의 나머지 출력.

하지만 시간이 너무 많이 걸려서

if(DT[can][a][b]==-1) DT[can][a][b] = (f(a+2, b+1, can) + f(a+1, b, can) ) % MOD;

return DT[can][a][b]

memset : memset(DT, -1, sizeof(DT)); => -1로 다 채움

코드:

#include <cstdio>
#include <cstring>
#define MOD 100000003
 
int n, k, DT[2][1010][1010];
int f(int a, int b, bool can){
    if(b==k) return 1;
    if(a>=n-can) return 0;
    if(DT[can][a][b]==-1)
        DT[can][a][b] = (f(a+2, b+1, can) + f(a+1, b, can) ) % MOD;
    return DT[can][a][b];
 
 
}
 
int main(){
    memset(DT, -1, sizeof(DT));
    scanf("%d%d", &n, &k);
    printf("%d", (f(1,0,0) + f(2,1,1))%MOD);
    return 0;
}