경우의 수 DP (BOJ 2482)

문제

색상환

알고리즘

1. N개의 색 중 K개를 선택하는 DP[선택하는 색][선택한 색의 개수]를 완성하는 걸 목표로 한다.
2. 선택하는 색의 수가 N 미만인 경우(i<N, j<=K)
   2-1. i번 째 색을 선택하지 않는 경우, 인접한 색을 선택한 경우의 수와 동일 (DP[i-1][j])
   2-2. i번 째 색을 선택하는 경우, 인접한 색을 선택하지 않고 j-1개의 색을 선택한 경우의 수와 동일(DP[i-2][j-1])
   2-3. i개의 색 중 j개를 선택하는 경우는 2-1과 2-2의 합과 같다. (DP[i][j] = DP[i-1][j] + DP[i-2][j-1])
3. 선택하는 색의 수가 N인 경우(i==N, j<=K)
   3-1. N번 째 색을 선택하지 않는 경우는 2-1과 동일 (DP[N-1][j])
   3-2. N번 째 색을 선택하는 경우는 이전 색은 물론 최초의 색도 선택하지 못하기에
   N-3개의 색 중 j-1개의 수를 선택하는 경우의 수와 동일 (DP[N-3][j-1])
   3-3. N개의 색 중 j개를 선택하는 경우는 3-1과 3-2의 합과 같다. (DP[N][j] = DP[N-3][j-1] + DP[N-1][j])

코드

#include <bits/stdc++.h>

using namespace std;

int N, K, MOD = pow(10, 9)+3;
int DP[1001][1001];

void input(){
    cin >> N >> K;

    for(int i=1; i<N; i++){
        DP[i][0] = 1;
        DP[i][1] = i;
    }
}

void buildDP(){
    for(int i=2; i<N; i++){
        for(int j=2; j<=K; j++){
            DP[i][j] = (DP[i-1][j] + DP[i-2][j-1])%MOD;
        }
    }

    DP[N][K] = (DP[N-1][K] + DP[N-3][K-1])%MOD;
}

void printDP(){
    for(int i=1; i<=N; i++){
        for(int j=1; j<=K; j++){
            cout << DP[i][j] << " ";
        }
        cout << endl;
    }

}

void output(){
    cout << DP[N][K] << endl;
}

void run(){
    input();
    buildDP();
    //printDP();
    output();
}

int main(){
    run();
    return 0;
}

후기

오랜 시간을 잡고 있어도 풀리지 않아, 답을 확인한 후 풀어냄
경우의 수로 이루어진 DP를 접한 경험이 적어서인지
답을 이해하는 데에도 시간이 오래 걸렸던게 문제..
아마 DP[N][K]를 N번 째 수를 선택하는 경우의 수로만 한정해서 그랬던 듯 싶다.
차차 나아지길