BAEKJOON 2482번: 색상환

문제링크: https://www.acmicpc.net/problem/2482

2482번: 색상환

D[i][j]={i개의 색 중, j개의 색 선택시 문제의 답} 이라고 정의하겠다.

 

D[i][j]를 점화식으로 표현하기 위해서

case1) i번째 색을 선택한다.

case2) i번째 색을 선택하지 않는다.

 

위와같이 케이스를 나누어서 생각했을때

D[i][j]= case1) + case2) 이다.

case1) 과 case2) 를 D로 나타내면 다음과 같다.

 

case1) D[i-2][j-1]

(i번째 색을 선택했으므로 i에 인접한 두 색을 선택할 수 없으며, 이미 i번째의 색 하나를 선택했기 때문에 j-1개 선택)

case2) D[i-1][j]

(i번째 색을 선택하지 않으며, j개의 색 선택)

 

따라서

D[i][j]=D[i-1][j]+D[i-2][j-1]

 

또한 i＜j×2일 경우에 인접하지 않게 j개를 고르는 것은 불가능하다. 따라서 이러한 경우는 계산하지 않는다.

 

위 풀이를 구현한 코드는 다음과 같다.

#include <cstdio>
#define FOR(i,s,n) for(int i=s;i<=n;i++)
int D[1003][1003],N,K,m=1e9+3;
int main(){
    scanf("%d%d",&N,&K);
    FOR(i,0,N)D[i][1]=i;
    FOR(j,2,K)FOR(i,1,N)if(i>=j*2)D[i][j]=(D[i-1][j]+D[i-2][j-1])%m;
    printf("%d",D[N][K]);
    return 0;
}

위 풀이의 경우 시간복잡도는 O(NK)이다.