[DP/ C++] BOJ 2482 색상환

문제 

문제 접근

우선 색상환의 개수를 dp에 사용할 수 있겠다는 생각을 했다. 그래서 dp 2차원 배열에서 dp[N][k]라고 생각해서 설계했다.

 

 

조합을 사용하는 풀이처럼 느껴져서 배낭문제와 비슷하게 풀이를 해야겠다고 생각을 했고, 경우를 두가지로 나눠서 생각했다.,

 

1) N번째 색을 택하는 경우 

N번째 색을 택하면 N-1번째 색은 택할 수가 없다. 따라서 N-2개 색 중 K-1개 색을 택하는 경우와 같다.

= dp[N-2][k-1]

 

2) N번째 색을 택하지 않는 경우

이 방법은 N-1개의 색에서 k개의 색을 택하는 경우와 같다.

= dp[N-1][k]

 

따라서 dp[N][k] = dp[N-2][k-1] + dp[N-1][k] 이다.

 

정답 코드

#include <iostream>

#define mod 1000000003
using namespace std;
int dp[1003][1003];

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, k;
    cin >> N >> k;

    for (int i = 0; i <= N; i++) {
        dp[i][1] = i;
        dp[i][0] = 1;
    }
    dp[2][2] = 0;
    for (int i = 4; i <= N; i++) {
        for (int j = 2; j <= k; j++) {
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % mod;
        }
    }
    cout << dp[N][k];
    return 0;
}