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

1. 문제

 

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

2482번: 색상환

 

2. recursive

일단 문제를 중복되는 작은 부분 문제들로 분할을 해보자

 

각 부분문제를 해결하는 함수를 다음과 같이 정의할 수 있다.

 

dp(count, idx) = count개의 색상이 선택되었고 idx 부터 색을 적절히 선택하여  

                                 n-1번 인덱스까지 K개를 선택할 수 있는 경우의 수

 

이 함수는 idx 색상을 선택하는 것과 선택하지 않는것 두가지 부분문제를 생성한다.

 

따라서 점화식으로 나타내면 다음과 같다

 

dp(count , idx) = dp(count + 1, idx + 2)  + dp(count, idx + 1)

 

이 문제는 0번째 색상을 선택하지 않으면 색상환을 선형띠로 생각하여 문제를 해결할 수 있다. 0 번째 색상을 선택하는 경우는 3번째 인덱스에서 시작하고 k-1개를 선택하는 선형으로 생각할 수 있다. (1개는 이미 선택)      - 0번을 선택하면 n-1을 선택하지 못한다.       - 2부터 시작해서 n-2까지 선택하는것과 동일      - 3부터 시작해서 n-1까지 선택하는 경우의 수와 동일     함수를 n-1번 인덱스까지 k개를 선택할 수 있는 경우의 수로 설정하였기 때문에 3~n-1 로 설정하였다. 따라서 문제를 해결하기 위해서 원형이라는 조건은 생각하지 않아도 되며 최종적으로 답은 dp(N, K, 0, 1) + dp(N, K, 1, 3) 이 된다.

 

* 여기서 (n - idx)/2 + 1 < k - count 를 검사하는것은 가지치기를 하는 것이다.  k개를 선택하지 못하는 경우 계산 하지않는다.

 

 

 

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
const int div1 = 1000000003;
int cache[501][1001];
 
int dp(int n, int k, int count, int idx) {
    int &ret = cache[count][idx];
    if(ret != -1) {
        return ret;
    }
    if(count == k) {
        return 1;
    }
    if(idx >= n ||  (n - idx)/2 + 1 < k - count ) {
        return ret = 0;
    }
 
    return ret = (dp(n, k, count + 1, idx + 2) + dp(n, k, count, idx + 1)) % div1;
}
 
int main() {
    int N, K;
 
    cin>>N>>K;
    if(N/2 < K) {
        cout<<0;
    }
    else {
        memset(cache, -1, sizeof cache);
        cout<<(dp(N, K, 0, 1) + dp(N, K, 1, 3))%div1<<"\n";
    }
}

3. iterative

https://stillchobo.tistory.com/102

백준 2482번 : 색상환

 

더 나은 풀이

=> idx를 옮기는 것이 아닌 n을 줄이면서 문제를 다른 문제 n-2에서 k-1 개를 찾는것과 n-1에서 k개를 찾는것으로 변형한 풀이

=> 이 풀이는 0번인덱스로부터 자유롭다.

https://kibbomi.tistory.com/124