BOJ 2482: 색상환

DP문제이다. 원형으로 구성된 문제는 상당히 골치아픈 것이, 맨 위와 맨 아래에 대한 중복체크를

해 주어야 한다. 그러나, "3차원 배열"이라는 한 단어에서 힌트를 얻어 풀이를 작성하면 정말 쉽게 풀 수 있다. 

 

dp문제는 언제나 문제를 dp식으로 모델링하는 것이 문제이다.

dp[i][j][k]를, i번째 원소까지, j개를 선택, 이 때 k=0: 현재를 선택하지 않음 / k=1: 현재를 선택함

으로 모델링하면 된다. 

이제, 포함 / 비포함으로 문제를 풀면 중복제거도 할 필요 없이 자연스레 문제가 풀린다.

첫 번째 식에서, dp[1][0][0]=0; dp[1][1][1]=1;은 1번째 원소를 반드시 선택하겠다는 뜻이 된다.

이 때에는 sum에 dp[N][K][0]만을 더해주면 된다.

다음 식에서, dp[1][0][0]=1; dp[1][1][1]=0;은 1번째 원소를 반드시 선택하지 않겠다는 뜻이 된다.

이 때에는 sum에 dp[N][K][1], dp[N][K][1] 모두 더해 주면 된다. 

즉, 한마디로 말하자면, "애초에 선택하는 경우에 대한 초기 경우의 수를 0으로 두기" / "애초에 선택하지 않는 경우에 대한 초기 경우의 수를 0으로 두기"라는 두 가지 갈래에 대한 덧셈만 구하면 그만인 것이다.

 

dp식은 너무 쉽게도,

dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1]

dp[i][j][1]=dp[i-1][j-1][0]이다.

왜 그런지는 스스로 생각해 보라. 물론 모듈러 덧셈이기에 INF를 어디서 나누던 상관은 없다. 필자는 이런 것을 생각하는 걸 별로 좋아하지 않기 때문에(사실 귀찮기 때문에) 매번 나누었다. 당연히 그래도 문제는 없다.

 

#include<bits/stdc++.h>
#define INF 1000000003
using namespace std;
typedef long long int ll;
ll N, K, dp[1001][1001][2], sum;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> K;
	dp[1][0][0]=0; dp[1][1][1]=1;
	for(int i=2;i<=N;i++){
		for(int j=0;j<=K;j++){
			if(j==0){
				dp[i][j][0]=dp[i-1][j][0]; 
				continue;
			}
			dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
			dp[i][j][0]%=INF;
			dp[i][j][1]=dp[i-1][j-1][0];
			dp[i][j][1]%=INF;
		} 
	}
	sum+=dp[N][K][0];
	sum%=INF;
	for(int i=0;i<1001;i++){
		for(int j=0;j<1001;j++){
			dp[i][j][0]=0;
			dp[i][j][1]=0;
		}
	}
	dp[1][0][0]=1; dp[1][1][1]=0; // 1번째 선택 X
	for(int i=2;i<=N;i++){
		for(int j=0;j<=K;j++){
			if(j==0){
				dp[i][j][0]=dp[i-1][j][0]; 
				continue;
			}
			dp[i][j][0]=dp[i-1][j][0]+dp[i-1][j][1];
			dp[i][j][0]%=INF;
			dp[i][j][1]=dp[i-1][j-1][0];
			dp[i][j][1]%=INF;
		} 
	}
	sum+=dp[N][K][1];
	sum%=INF;
	sum+=dp[N][K][0];
	sum%=INF; // modular 연산에 대한 덧셈 법칙 
	cout << sum;
}