[동적 계획법 3 단계] 백준 2482번 색상환

문제

색을 표현하는 기본 요소를 이용하여 표시할 수 있는 모든 색 중에서 대표적인 색을 고리 모양으로 연결하여 나타낸 것을 색상환이라고 한다. 미국의 화가 먼셀(Munsell)이 교육용으로 고안한 20색상환이 널리 알려져 있다. 아래 그림은 먼셀의 20색상환을 보여준다.

그림 1. 먼셀의 20색상환

색상환에서 인접한 두 색은 비슷하여 언뜻 보면 구별하기 어렵다. 위 그림의 20색상환에서 다홍은 빨강과 인접하고 또 주황과도 인접하다. 풀색은 연두, 녹색과 인접하다. 시각적 대비 효과를 얻기 위하여 인접한 두 색을 동시에 사용하지 않기로 한다.

주어진 색상환에서 시각적 대비 효과를 얻기 위하여 서로 이웃하지 않은 색들을 선택하는 경우의 수를 생각해 보자.  먼셀의 20색상환에서 시각적 대비 효과를 얻을 수 있게 10개의 색을 선택하는 경우의 수는 2이지만, 시각적 대비 효과를 얻을 수 있게 11개 이상의 색을 선택할 수 없으므로 이 경우의 수는 0이다.

주어진 정수 N과 K에 대하여, N개의 색으로 구성되어 있는 색상환 (N색상환)에서 어떤 인접한 두 색도 동시에 선택하지 않으면서 서로 다른 K개의 색을 선택하는 경우의 수를 구하는 프로그램을 작성하시오.

입력

입력 파일의 첫째 줄에 색상환에 포함된 색의 개수를 나타내는 양의 정수 N(4≤N≤1,000)이 주어지고, 둘째 줄에 N색상환에서 선택할 색의 개수 K(1≤K≤N)가 주어진다. 

출력

첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.

 

dp[N][K]를 N개의 색에서 K개를 칠하는 경우의 수라고 했을 때

dp[i][j]로 부터 dp[N][K]를 만드는 과정으로 구할 수 있다.

우선 초기화는 어떤 i에 대해서도 1개를 칠하는건 i가지 0개는 1가지 이므로 초기화 해 줌.

dp[i][j]는 N개에 속한 i번째 컬러를 바라보는 관점으로 이 컬러를 칠하거나 칠하지 않거나로 경우의 수를 구할 수 있음.

칠한다면 자신과 자신의 앞을 제외하고 j-1개 , 칠하지 않는다면 자신을 제외하고 j개

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

 

그리고 N에 다다라서는 별도의 처리를 해줘야 한다.

N은 1과도 동시에 색칠되면 안되므로 칠한다면 dp[N-3][j-1]

안칠한다면 dp[N-1][j]가 된다.

#include <iostream>
#include <vector>
#include<string.h>
#include<queue>
#include <string>
#include<stack>
#include<cmath>
#include <map>
#include<algorithm>
using namespace std;

const int MOD = 1000000003;
int N, K;
int dp[1001][1001];
//dp[N][K] => N개중 K개 뽑는 경우의 수 
int main() {
	cin >> N >> K;
	for (int i = 0; i <= N; i++)
	{
		dp[i][1] = i;
		dp[i][0] = 1;
	}

	//i번째를 바라보고 있을 때 경우의 수 
	//i번째를 포함 or 포함 x
	for (int i = 2; i <= N; i++)
	{
		for (int j = 2; j <= K; j++)
		{
			dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % MOD;
		}
	}
	
	//N에서는 1까지 고려해서 생각해야 함.
	// N-1,N,1 제외 
	int ans = (dp[N - 3][K - 1] + dp[N - 1][K]) % MOD;
	cout << ans << endl;
	
}