[백준] 2482번 색 상환 [C++]

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

2482번: 색상환

---

문제

 

---

접근 방식

DP라는 이중 배열을 만들건데, DP[N][M]의 형태로 만든다. 여기서 N은 색상환의 갯수, M은 선택할 색상의 갯수이다.

처음에 두개의 예외처리를 해줘야 하는데,

• N개의 색 상환에서 1개의 색을 고른다고 가정해보자면, 경우의 수는 N개가 나온다. 따라서 M이 1일 때  DP[N][1] = N이라는 공식을 만족하게 된다.
• 문제에서 언급한 예시인데, 색상환의 갯수가 선택할 색의 2배보다 작을 경우, 선택할 경우의 수가 없어진다. 이러한 경우도 예외처를 해준다.

다음으로 점화식이다. 내가 N의 갯수를 1개씩 늘린다고 가정한다면 가능한 경우는

(이번에 추가된 색 상환을 포함한 경우) + (이번에 추가된 색 상환이 포함되지 않은 경우) 로 나눌 수 있다.

전자의 경우에는 이번꺼를 포함시킨다면, 선택해야 할 숫자는 M-1이 되고, 바로 이전의 색상환을 포함시키면 안되니까

DP[N-2][M-1]이 된다.

후자의 경우는 선택해야 할 숫자는 M이고, 바로 이전의 색상환 까지 포함을 시켜도 되니 DP[N-1][M]이 된다.

따라서 DP[N][M]=DP[N-2][M-1]+DP[N-1][M]을 만족하게 된다.

---

코드

 

#include <iostream>
using namespace std;
int dp[1001][1001];
int n, m;
int dpf(int x, int y) {
	if (dp[x][y] != -1)return dp[x][y];
	if (y * 2 > x)return 0;//두번 째 예외
	dp[x][y] = (dpf(x - 2, y - 1) + dpf(x - 1, y)) % 1000000003;
	return dp[x][y];
}
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		dp[i][1] = i; //첫번째 예외
			for (int j = 2; j <= m; j++) {
				dp[i][j] = -1;
			}
	}
	cout << dpf(n, m);
}

---

 

약간의 예외를 미리 처리하면 큰 어려움이 없는 DP문제였다.