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

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

2482번: 색상환

 

DP 문제다.

 

원형 칸에서 나란하지 않은 k개를 고르는 경우의 수를 구하는 문제다.

몇가지 계산하다보니 바로 규칙을 찾을 수 있었다.

행이 n, 열이 k일 때 아래와 같은 표를 그릴 수 있다.

	1	2	3	4
4	4	2	0	0
5	5	5	0	0
6	6	9	2	0
7	7	14	7	0

 

표를 통해 dp[i][j] = dp[j - 1][i] + dp[j - 2][i - 1]와 같은 점화식을 세울 수 있다.

 

#include <iostream>
using namespace std;

int n, m;
int dp[1001][1001];

int main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) dp[i][1] = i;

	for (int i = 2; i <= m; i++) {
		for (int j = 1; j <= n; j++) {
			if (j / 2 >= i) dp[j][i] = (dp[j - 1][i] + dp[j - 2][i - 1])%1000000003;
		}
	}

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