(c++) 동적계획법 2482번: 색상환

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

2482번: 색상환

 

 

 

 

문제 개요

 

 

 

원형일 경우에 동적계획법을 사용하는 문제이다.

 

문제에 대한 점화식을 만든다면 쉽게 풀 수 있는 문제이다. (이게 가장 어렵다.)

 

메모이제이션은 n = 색깔의 개수,  k = 선택 개수라고 할 때의 경우의 수를 저장하면 되고,

색깔의 개수인 n에 대해서 n을 선택한 경우 + n을 선택하지 않는 경우로 점화식을 만든다. 

 

$$ d[n][k] = d[n-1][k] + d[n-2][k-1] $$

 

문제가 원형으로 주어질 경우 많이 사용하는 점화식이라고 한다.

 

재귀를 할 경우 n과 k의 관계를 보아야 하는데

n을 2로 나눈 몫보다 k가 큰 경우 경우의 수가 0이 나오는 경우를 기저식으로 넣고,

n이 0이 아니면서 k가 1인 경우 n의 수를 리턴해주면 코드가 완성된다.

 

 

 

 

코드

 

 

 

#include <bits/stdc++.h>
#define MOD 1000000003

using namespace std;

int n, k;
long long cache[1001][500];

// start = 색깔 수, num = 선택할 수
long long mun(int start, int num) {
    // 해당 경우 반복을 끝낸다.
    if (start != 0 && num == 1) return start;
    else if ((start / 2) < num) return 0;
    long long& ret = cache[start][num];
    if (ret != -1) return ret;
    ret = 0;
    // mun(n, k) = mun(n-1, k) + mun(n-2, k-1)
    ret = (mun(start-1, num) % MOD) + (mun(start-2, num-1) % MOD);
    return ret;
}

int main(void) {
    cin >> n;
    cin >> k;
    memset(cache, -1, sizeof(cache));
    cout << mun(n, k) % MOD;
}