백준 2482 - 색상환

 

문제 링크: https://acmicpc.net/problem/2482 

2482번: 색상환

---

문제를 요약해봅시다.

• \(N\)개의 색이 원형으로 배치된 색상환에서 \(K\)개의 색을 골라야 합니다. 이때 \(K\)개의 색은 서로 인접하지 않아야 합니다.
• \(K\)개를 고르는 경우의 수를 계산하고, \(10^9 + 3\)으로 나눈 나머지를 출력합니다.

---

- 풀이

어떻게 풀어야 할지 감이 잘 안 잡히는 문제입니다.

우선, \(N\)개의 색 중 \(K\)개를 인접하지 않게 고르는 것이 가능한 지부터 따져봅시다. 그러려면 \(N\)개의 색이 있을 때 최대로 고를 수 있는 색의 개수를 구해야 하겠죠.

색을 서로 인접하지 않게 고르려면, 색을 하나 고르고 그 다음 색은 절대 고르지 않는 방법을 취하면 됩니다. 만약 색 \(1\)을 고르면 색 \(2\)는 절대 고르면 안되겠죠!

이런 방법대로 생각해 보면 \(N\)개 색 중에서는 \(\frac{N}{2}\)개 이하인 가장 큰 자연수, 즉 \(\lfloor \frac{N}{2} \rfloor\)개 까지의 색을 고를 수 있음을 알 수 있습니다. 만약 \(K\)가 이보다 크다면 \(0\)을 출력하기만 하면 되겠군요!

 

- 다이나믹 프로그래밍: \(O(N^3)\)

그러면 이제 일반적인 경우를 생각해 봅시다. 경우의 수를 전부 다 따지는 것은 어렵기 때문에 다이나믹 프로그래밍을 사용합니다.

우선 2차원 배열 \(dp\)를 생각해봅시다. \(dp[i][j]\)는 색을 \(i\)개 사용했을 때 마지막 색의 번호가 \(j\)인 경우의 수라고 하겠습니다.

먼저 색을 1개 사용했을 때의 경우의 수는 전부 1이므로 \(dp[1][x] = 1\)입니다. \((1\leq x\leq N)\)

그리고, 이런 점화식을 이끌어 낼 수 있습니다.

\[dp[i][j] = \sum_{k=1}^{j-2}dp[i-1][k]\]

왜 이런 식을 세울 수 있을까요? 차근차근 따져봅시다.

• \(dp[i][j]\)는 색을 \(i\)개 사용했을 때 마지막 색의 번호가 \(j\)인 경우의 수를 말합니다. 그렇다면 색을 \(i - 1\)개 사용했을 때는 마지막 색이 \(1, 2, ..., j - 3, j - 2\)인 경우를 생각해 볼 수 있습니다.
• 색들 사이에는 공간이 최소 1개만 있으면 되기 때문에 색을 \(i - 1\)개 사용했을 때 마지막 색이 \(1, 2, ..., j - 3, j - 2\)인 경우가 전부 다 가능합니다. 따라서 \(dp[i - 1][1] + dp[i - 1][2] + ... + dp[i - 1][j - 2] = \sum_{k=1}^{j-2}dp[i - 1][k]\)라는 식을 세울 수 있습니다.

 

이렇게 계산을 반복해서 \(dp[K][x]\)의 값을 전부 구한 뒤 다 더해주기만 하면 됩니다.

하지만 중요한 부분이 있습니다. 색상환은 원 형태이므로 \(dp[K][N]\)의 값을 더할 때는 첫 번째로 고른 색이 색 \(1\)인 경우를 빼줘야 합니다!

마지막 색인 색 \(N\)은 색 \(1\)과 같이 선택하면 안되기 때문입니다. 이를 해결하려면 \(dp[i][j]\)의 값을 다음과 같이 확장해주면 됩니다.

\[dp[i][j] = (첫 색이  1인 경우, 첫 색이  1이 아닌 경우)\]

계산을 할 때 두 경우를 나눠서 더해주면 마지막에 \(dp[K][N]\)을 더할 때 색 \(1\)로 시작한 경우의 수를 뺄 수 있습니다.

 

여기까지 했다면 답은 올바르게 나옵니다. 시간복잡도를 계산해보면, \(dp[i][j]\)를 \(O(KN)\)번 계산해야 하고, 각 계산마다 \O(K)\)번의 덧셈을 사용하므로 총 시간복잡도는 \(O(NK^2) = O(N^3)\)입니다.

\(N\leq1000\)이므로 \(O(N^3)\)의 시간복잡도로는 시간 안에 문제를 해결할 수 없습니다. 어떻게 최적화하면 좋을까요?

 

- 최적화: \(O(N^2)\)

점화식 \(dp[i][j] = \sum_{k=1}^{j-2}dp[i -1][k]\)를 계산하는 과정을 살펴봅시다. 잘 보면 다음이 성립합니다.

\[dp[i][j + 1] = \sum_{k=1}^{j-1}dp[i-1][k] = \sum_{k=1}^{j-2}dp[i-1][k] + dp[i-1][j-1] = dp[i][j] + dp[i - 1][j - 1]\]

즉, 각각의 \(dp[i][j]\)를 계산할 때마다 \(j-2\)번의 반복을 할 필요가 없습니다! 점화식을 더 간단하게 만들 수 있습니다.

\[dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 2]\]

이때의 시간복잡도는 \(O(KN) = O(N^2)\)입니다.

 

추가로, 점화식을 잘 살펴보면 \(dp[i][j]\)를 계산할 때 \(dp[i][j - 1]\)과 \(dp[i - 1][j - 2]\)만이 필요한 것을 알 수 있습니다.

즉 \(dp[i - 2], dp[i - 3], ...\)은 계산에 필요하지 않습니다!

따라서, \(dp\) 배열을 2차원으로 선언하는 대신, 1차원 배열로 선언하여 메모리 사용량을 더 줄일 수 있습니다.

---

여담으로, 이 문제는 조합론으로도 풀 수 있습니다. 고등학교 수학에서 나오는 어려운 경우의 수 문제입니다.

색 \(K\)개를 반드시 골라야 하니 \(K\)개의 물건이 있다고 가정하고, 그 사이에 빈칸(선택하지 않는 색)을 끼워넣는 경우의 수를 고르는 것입니다.

구체적인 접근법은 다음과 같습니다.

• 문제에서 \(K\)개의 색은 이미 골라졌다고 생각하고, \(K\)개의 선택하지 않은 색을 각 색의 뒤에 배치했다고 생각해봅시다.
• 남은 색은 \(N - 2K\)개이고, 이를 배치할 수 있는 공간은 \(K\)개 색들 사이의 총 \(K\)개 공간입니다.
• \(N - 2K\)개의 색을 \(K\)개 공간에 배치할 수 있는 경우의 수를 계산하면 됩니다.

단 계산이 조금 까다로울 수 있다고 생각합니다. 색 \(N - 2K\)개를 \(K\)개 이하로 나누는 문제가 되므로 자연수의 분할을 생각해보세요.

---

마지막으로 어떤 방식으로 문제를 풀든 32비트 정수형은 오버플로우가 일어날 수 있다는 사실을 잊지 말도록 합시다.

 

소스코드 (C++, 다이나믹 프로그래밍)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;

constexpr ll mod = 1e9 + 3;

class Node {
public:
    // 색 1로 시작하는 경우의 수
    ll z = 0;
    // 색 1로 시작하지 않는 경우의 수
    ll nz = 0;
    
    Node() {}
    Node(ll z, ll nz) {
        this->z = z;
        this->nz = nz;
    }
    
    Node operator+(const Node &n) const {
        return Node((this->z + n.z) % mod, (this->nz + n.nz) % mod);
    }
};

int main() {
    fastio;
    
    int n, k;
    cin >> n >> k;
    
    if (k > n / 2) {
        cout << 0;
        return 0;
    }
    
    vector<Node> dp(n, Node(0, 1));
    dp[0] = Node(1, 0);
    
    // 이전 값을 이용해 점화식을 계산합니다.
    for (int i = 1; i < k; i++) {
        vector<Node> next_dp(n);
        
        for (int j = 2; j < n; j++) {
            next_dp[j] = next_dp[j - 1] + dp[j - 2];
        }
        
        dp = next_dp;
    }
    
    // 첫 색과 마지막 색을 동시에 고르는 경우의 수를 제외합니다.
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (i < n - 1) {
            ans += dp[i].z;
            ans %= mod;
        }
        ans += dp[i].nz;
        ans %= mod;
    }
    cout << ans;
    
    return 0;
}