백준 2449번: 전구 [C++]

작성일 | In
플래티넘 III 플래티넘 III

문제

전구

풀이

입력으로 주어진 $i$번째 전구의 색을 $C_i$라 합시다.

$DP[i][j]$를 구간 $[i, j]$를 모두 $C_i$로 만드는 데 필요한 최소 횟수로 정의합시다. 그렇다면 다음 점화식을 통해 $DP$를 구할 수 있습니다.

\[\begin{align} f(x, y) &= \begin{cases} 1 & \text{if } C_x \ne C_y \\ 0 & \text{else} \end{cases} \\ DP[i][j] &= \min(DP[i][k] + DP[k + 1][j] + f(i, k + 1)) \end{align}\]

$C_i = C_{k + 1}$이라면 둘을 각각 $C_i$로 만들면 통일이 되고, 그렇지 않다면 각각 $C_i$와 $C_{k + 1}$로 통일한 후 $C_i$로 통일합니다.

구간 $[i, j]$를 하나로 통일할 때에는 $C_i$ 또는 $C_j$로 통일하는 것이 최선이고 둘 모두 필요한 횟수는 같습니다. 따라서 $DP[1][N]$이 답이 됩니다.

증명

연속된 전구가 같은 색을 갖는다면 어느 전구의 색을 바꾸더라도 색이 같이 바뀌므로 하나의 전구로 압축하여 볼 수 있습니다. 따라서 연속된 전구가 같은 색을 갖지 않는다고 가정합시다. 따라서 임의의 자연수 $n$에 대해 $C_n \ne C_{n + 1}$ 입니다.

구간 $[i, j]$를 어떤 색 $c$로 통일하는 것은 구간 $[i + 1, j - 1]$을 색 $c$로 통일한 다음 나머지 $i$번째 전구와 $j$번째 전구를 $c$로 통일하는 것과 같습니다. $c \ne C_i$이고 $c \ne C_j$일 때 $C_i$ 혹은 $C_j$로 통일하는 것이 최선임을 증명해 보겠습니다.

$C_i \ne C_j$라면 $i$번째 전구와 $j$번째 전구를 각각 $c$로 바꾸는 경우와 $[i + 1, j - 1]$을 $C_i$와 $C_j$중 하나로 바꾸고 하나로 통일하는 경우 모두 $2$회를 더 필요로 합니다.

$C_i = C_j$라면 $[i + 1, j - 1]$을 모두 $C_i$로 바꾸는 것이 최선입니다.

코드

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
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
#ifndef ONLINE_JUDGE
#define ASSERT(x) assert(x)
#else
#define ASSERT(ignore) ((void)0)
#endif

using namespace std;

int dp[222][222];
// dp[i][j] represents the minimum number of operations needed to make all bulbs
// in [i, j] be the same color

int color[222];

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

    int N, K;
    cin >> N >> K;

    fill(&dp[0][0], &dp[N][N + 1], N);

    for (int i = 1; i <= N; i++) {
        cin >> color[i];
        dp[i][i] = 0;
    }

    for (int len = 2; len <= N; len++) {
        for (int i = 1; i <= N - len + 1; i++) {
            int j = i + len - 1;

            for (int k = i; k < j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] +
                                             (color[i] != color[k + 1]));
            }
        }
    }

    cout << dp[1][N];

    return 0;
}

백준 2449번: 전구 [C++]