[백준] 2482-색상환(C++)

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

2482번: 색상환

 

dp문제입니다. 점화식을 생각하는데 오래 걸렸습니다.

 

인접하게 칠할 수 없다는 조건이 있습니다.

 

dp[N][K] = N 개 짜리 색에서 K 개를 인접하지 않게 칠하는 경우의 수

 

점화식 : dp[n][k] = dp[n-2][k-1] + dp[n-1][k] 

 

 

표를 작성하면서 해당 점화식 규칙을 알게 되었습니다. 두개이상의 색을 구할때는 색칠한 경우와 하지 않은 경우로 구분하여 생각하면 됩니다. 

 

아래는 정답코드입니다.

#include <iostream>
using namespace std;

int dp[1001][1001] = { 0 };
int n = 0, k = 0;
int result = 0;

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> k;

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

	return 0;
}