[2449] 전구

문제 링크 : https://www.acmicpc.net/problem/2449

2449 - 전구

본문

최대 $K$가지의 서로 다른 색을 표현할 수 있는 전구들이 있다. 이 전구 $N$개를 다음의 그림과 같이 한 줄로 배치하여 서로 연결한다. (동그라미 안의 숫자는 전구의 색을 의미한다)

각 전구는 스위치가 있어서 전구의 색을 임의의 색으로 바꿀 수 있다. 하나의 전구 색을 바꾸는 경우에는, 색이 바뀌는 전구에 인접한 전구가 같은 색이면, 이 전구의 색도 같이 바뀌게 되며 인접한 전구가 다른 색이 나올 때까지 계속 바뀌게 된다. 예를 들어, 위의 그림에서 $4$번 전구의 색을 2번 색으로 바꾸면, $5$번 전구가 $4$번 전구와 같은 색이었으므로 2번 색으로 바뀌고, $6$번 전구도 $5$번 전구와 같은 색이었으므로 2번 색으로 바뀌게 된다. 즉, $4$번 전구의 색을 2번 색으로 바꾸면, 연결된 같은 색의 모든 전구인 $4, 5, 6$번의 전구가 2번 색으로 바뀌게 되어 아래의 그림과 같이 된다.

전구의 수 $N$과 $N$개의 전등에 대한 초기 색이 주어질 때, 모든 전구의 색이 하나로 같아질 때까지 최소 몇 번 전구의 색을 바꾸어야 하는지를 구하는 프로그램을 작성하시오. 단, 전구의 각 색은 1부터 $K$까지의 정수로 나타낸다.

입력

입력의 첫 번째 줄에는 전구의 수를 나타내는 양의 정수 $N$과 전구가 표현할 수 있는 색의 수 $K$가 주어진다. 단, $N$은 $1$이상 $200$이하의 정수이며, $K$는 $1$이상 $20$이하의 정수이다. 두 번째 줄에는 $N$개 전구의 색이 전구번호의 순서대로 하나의 정수로 하나의 빈칸을 사이에 두고 주어진다.

출력

첫째 줄에 모든 전구의 색이 하나로 같아질 때까지 전구의 색을 바꾸는 횟수의 최솟값을 하나의 정수로 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

어떤 조건을 만족하기 위한 최소 횟수를 찾는 문제. 그리고, 큰 문제를 여러 작은 문제로 쪼개서 생각할 수 있는 문제. 그렇다면 유용하게 사용할 수 있는 방법이 dp일 것이다. 그래서 일단 직관적인 dp로 문제를 해결해보려 한다.

색이 같은 구간을 하나의 그룹으로 생각하고, 이들은 한번에 색깔이 변경되므로, dp에서 구간을 이용한 index가 필요할 것 같다. (dp[start][end])

그리고, 그 구간이 현재 어떤 색깔인지도 기록할 필요가 있을 것 같다. (dp[start][end][color])

그렇게 만들어진 dp배열은 dp[start][end][color]. 크기가 $200 \times 200 \times 20 = 80\,000$이다. 생각보다 많이 널널하다. 그래서 추가적인 dp 조절 없이 이대로 진행해보자.

점화식의 경우, dp배열의 의미를 “구간의 시작과 끝의 전구의 모든 색을 color 색으로 변경하는데 필요한 최소 횟수”로 놓고 보면, 아래와 같은 정보를 얻을 수 있음을 알 수 있다.

• 구간의 길이가 1인 경우 (start = end), 바꾸려는 color가 현재 전구 색과 같다면 $0$, 아니라면 색을 변경해야하므로 $1$이다
• 구간의 길이가 1이 아닌 경우 (start < end), 구간 내의 한 노드 $i$를 잡고, 모든 색깔 $c$에 대해 dp[s][e][c] = min(dp[s][i][c] + dp[i + 1][e][c])이다.
  • 이 때, 구간 [s][i]와 구간 [i + 1][e]의 색깔이 $c$가 아닐 경우, 각각의 경우에 $+1$을 해주어야한다.

이 정보들을 이용하여 구현하면 답을 얻을 수 있다. 시간복잡도는 $O(N^3 \times K^2)$. 생각보다 직관적이고 난이도가 어렵지 않은 문제였다.

• 참고 알고리즘 : 다이나믹 프로그래밍

코드

사용 언어 : C

최종 수정일 : 2023 / 3 / 23

#include <stdio.h>

#define MAX_IDX 200
#define MAX_COLOR (20 + 1)
const int INF = 987654321;

int n, k;
int arr[MAX_IDX];
int dp[MAX_IDX][MAX_IDX][MAX_COLOR];

#define min(a, b) (((a) > (b)) ? (b) : (a))

void init() {
    for (int a = 0; a < n; ++a) {
        for (int b = 0; b < n; ++b) {
            for (int c = 1; c <= k; ++c) {
                dp[a][b][c] = INF;
            }
        }
    }

    return;
}

int solve(int s, int e, int c) {
    if (dp[s][e][c] < INF) {
        return dp[s][e][c];
    } else if (s == e) {
        return dp[s][e][c] = ((arr[s] == c) ? 0 : 1);
    } else {
        int ret = INF;
        for (int i = s; i < e; ++i) {
            int temp = ((arr[s] == c) ? 0 : 1) + ((arr[i + 1] == c) ? 0 : 1);
            ret = min(ret, solve(s, i, arr[s]) + solve(i + 1, e, arr[i + 1]) + temp);
        }
        return dp[s][e][c] = ret;
    }
}

int main() {
    scanf("%d %d", &n, &k);
    for (int i = 0; i < n; ++i) {
        scanf("%d", arr + i);
    }

    init();

    int ret = INF;
    for (int i = 1; i <= k; ++i) {
        ret = min(ret, solve(0, n - 1, i));
    }

    printf("%d", ret);
    return 0;
}