[DP #18] (BOJ 2482) 색상환

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

2482번: 색상환

입력

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

출력

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

 

---

접근법

DP[i][j]를 i개 색을 이용해서 4개를 선택하는 가지수를 의미한다고 가정하자.

일단, 모든 경우를 구해봤다.

DP[8][4]의 DP[5][3]은 오타 / DP[6][3]이 맞음

그냥 무지성으로 패턴을 찾으려고 했다.

그래서, DP[i-1][j] + dp[i-2][j-1] 라는 점화식을 도출했다.

 

근데, DP적으로 문제를 해결하지않아서 DP적으로 접근해보려고 했다.

 

우선, N=6일때를 생각해봤다.

4를 중점으로 보자.

DP[4][2]에 대해서, 4는 두가지 경우가 가능하다.

 

1) 4가 포함되는 경우
2) 4가 포함되지 않는 경우

 

먼저 2) 4가 포함되지 않는 경우 먼저보자.

간단하다, DP[4-1][2]이다.

(이전까지 경우의 수를 그대로 가져간다.)

 

1) 4가 포함되는 경우를 보자.

4가 포함되려면 이전까지의 경우의 수를 가져가야한다.

그러나 (4-1)인 3은 인접했기 때문에 조건에 부합하지 않기 때문에

(4-2)인 2의 경우의 수를 가져간다.

이때, 4를 포함해서 2개의 색이 되어야 하기 때문에

DP[4-2][1]을 가져가야 한다.

 

따라서, DP[4][2] = DP[3][2] + DP[2][1]

 

이를 통해 점화식을

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

로 도출할 수 있다.

 

그리고 DP[i][1]에 대해서 i로 초기화해야한다.

DP[i][2]의 경우에 사용하기 때문

(1개 색상환을 구하는 것은 각 색을 하나씩 뽑는거라 똑같음)

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define MAX 1000000

using namespace std;


int n, k;
long long dp[1001][1001];

void init() {
	for (int i = 2; i <= n; i++) {
		dp[i][1] = i;
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> k;
	init();


	for (int i = 2; i <= n; i++) {
		for (int j = 2; j<=k; j++) {
			//cout << i << ", " << j << endl;
			dp[i][j] = dp[i - 1][j] + dp[i - 2][j - 1];
			//cout << dp[i][j] << endl;
			dp[i][j] %= 1000000003;
		}
	}

	cout << dp[n][k];
}

처음에 너무 무지성으로 패턴만 찾으려고 한것같다.

DP는 DP적으로 해결하자;;;