[백준] 2482번 색상환

[적용한 알고리즘]

DP

 

[아이디어]

1번과 N번이 둘 다 색칠되는 경우를 제외하고는, 나머지 경우는 선형으로 생각해줘도 된다.

 

dp[N][K] = N 개 짜리 색상환을 중 K 개를 인접하지 않게 칠하는 경우의 수

 

두 가지 경우로 나눌 수 있는데,

현재 i 번째 칸을 보고 있고

j 개의 칸을 칠했다고 하면,

 

1. i 번째 칸을 칠하는 경우 = dp[i - 2][j - 1]

2. 안칠하는 경우 = dp[i - 1][j] 

 

이므로, dp[i][j] = dp[i - 2][j - 1] + dp[i - 1][j] 다

 

이때 문제가 되는게 dp[n][k] 인데,

dp[n][k] 면 

 

1. N번째 칸을 칠하는 경우

1 번 칸을 칠해서는 안되고, N - 1번 칸도 칠하면 안되므로,

2 ~ N - 1 까지의 칸을 K - 1개의 색을 인접하지 않게 칠하는 경우와 같으므로,

dp[N-3][K - 1] 개이다

 

2. N번째 칸을 칠하지 않는 경우

1 ~ N - 1 까지 K 개의 색을 인접하지 않게 칠하는 경우와 같으므로,

dp[N - 1][K] 이다

 

따라서, dp[N][K] = dp[N - 3][K - 1] + dp[N - 1][K] 으로 구할 수 있다.

 

[교훈]

오랜만에 재밌는 확통 문제 푼 느낌이다.

 

<코드>

#include <cstdio>
#include <algorithm>
using namespace std;
const int mod = 1000000003;
int dp[1001][1001];
int N, K;

int main(){
    scanf("%d %d", &N, &K);
    for (int i = 0; i <= N; i++){
        dp[i][1] = i;
        dp[i][0] = 1;
    }

    for (int i = 2; i <= N; i++){
        for (int j = 2; j <= K; j++){
            dp[i][j] = (dp[i - 2][j - 1] + dp[i - 1][j]) % mod;
        }
    }

    int ans = (dp[N - 1][K] + dp[N - 3][K - 1]) % mod;
    printf("%d\n", ans);

    return 0;
}