본문 바로가기

Algorithm/BOJ (백준)

[C++] 백준 2482 색상환

2482 색상환

 

2482번: 색상환

첫째 줄에 N색상환에서 어떤 인접한 두 색도 동시에 선택하지 않고 K개의 색을 고를 수 있는 경우의 수를 1,000,000,003 (10억 3) 으로 나눈 나머지를 출력한다.

www.acmicpc.net

C++

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

#define MOD 1000000003
int DP[1003][1003];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 0; i <= n; i++) {
        DP[i][1] = i;
        DP[i][0] = 1;
    }

    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] % MOD << '\n';

    return 0;
}

 

DP[i][j]는 i개의 색상환에 포함된 색 중 j개의 색을 선택할 때 고를 수 있는 경우의 수다.

 

i개 색 중 1개를 택하는 경우의 수는 i개, i개 색 중 0개 색을 택하는 경우의 수가 1개인 것은 쉽게 알 수 있으므로 초기화해준다.

 

색상환을 선형으로 펼쳐서 생각한다면, 다음의 표와 같이 두 경우로 나누어 나타낼 수 있다.

첫번째 열은 i번째 색을 선택한 경우고, 두번째 열은 i번째 색을 선택하지 않은 경우이다.

 

1 2 ... i-2 i-1 i
j-1 개 선택 (선택 못함) O
j 선택 X

i번째 색을 선택한 경우에는 i-1번째 색은 자동으로 선택하지 못하고, 나머지 1 ~ i-2번째 색 중에서 j-1개의 색을 택하는 경우와 같을 것이다.

i번째 색을 선택하지 않은 경우에는 1 ~ i-1번째 색 중에서 j개의 색을 택하는 경우와 같을 것이다. 

 

따라서 점화식을 DP[i][j] = DP[i-2][j-1] + DP[i-1][j]와 같이 나타낼 수 있고, modulo 연산의 속성에 의해 한번 계산할 때마다 1,000,000,003으로 나눈 나머지를 넣어주면 전체 경우의 수를 1,000,000,003으로 나눈 경우의 수와 같게 된다.