백준 2482번: 색상환 [C++]

작성일 | In
골드 III 골드 III

문제

색상환
길이가 $n$인 원형 배열에서 $k$개의 원소(색)를 이웃하지 않게 고르는 경우의 수를 구하는 문제입니다.

풀이

원형의 배열이 아니라 그냥 선형의 배열이었다면 점화식을 쉽게 세울 수 있습니다.
$dp[i][j] = dp[i-2][j-1] + dp[i-1][j]$
$i$는 배열의 길이, $j$는 고르는 수의 개수, $dp[i][j]$는 그 경우의 수 입니다.
이전 기준으로 고르거나, 고르지 않거나 두 경우로 나누어 생각하면 됩니다.

그러나 이 문제가 다른 DP문제보다 까다로운 이유는 배열이 원형이라는 데 있습니다. 배열이 원형이므로 1번째 색과 n번째 색을 동시에 고를 수 없습니다. 그래서 1번째 색과 n번째 색을 예외처리 해 줍시다.

  1. 1번째 색을 고르고 n번째 색을 고르지 않는다.
  2. 둘 다 고르지 않는다.
  3. 1번째 색을 고르지 않고 n번째 색을 고른다.

1번과 2번을 합한 경우는 $n$번째 색을 선택하지 않으면서 $k$개의 색을 선택하는 경우이므로
$dp[n-1][k]$로 나타낼 수 있습니다.

3번의 경우에는 $1$번째 색, $n$번째 색과 $n-1$번째 색을 제외한 $n-3$개의 배열에서 $k-1$개의 색을 고르는 경우의 수와 같습니다.
따라서 $dp[n-3][k-1]$로 나타낼 수 있습니다.

따라서 우리가 구하려는 답은
$dp[n][k] = dp[n-1][k] + dp[n-3][k-1]$입니다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll dp[1000][1001];


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);


    int n, k;
    cin >> n >> k;

    for (int i = 1 ; i < n ; i++) {
        dp[i][0] = 1;
        dp[i][1] = i;
    }

    for (int i = 2 ; i < n ; i++) {
        for (int count = 2 ; count <= k ; count++) {
            dp[i][count] = (dp[i-2][count-1] + dp[i-1][count]) % 1000000003;
        }
    }

    cout << (dp[n-1][k] + dp[n-3][k-1]) % 1000000003;


    return 0;
}

여담

$dp[i][0] = 1$인 이유는 안 뽑는 경우가 1이기 때문입니다.
$_nC_0 = 1$이니까요.

백준 2482번: 색상환 [C++]