[BOJ] 백준 2449 전구 Python

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개 전구의 색이 전구번호의 순서대로 하나의 정수로 하나의 빈칸을 사이에 두고 주어진다.

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

---

문제풀이
예제에서는 10 3 으로 전구의 수와 표현가능색이 적게 주어지지만  200 20으로 주어진다면 전구의 색깔을 바꿀 수 있는 경우의 수가 너무 많아져 완전 탐색으로 이 문제를 푼다는 것은 불가능해보였다.
이렇게 경우의 수가 너무 많다고 느껴질 때 떠올려야하는 것이 DP이다.
이 문제는 모든 전구의 색이 하나로 같아질 때까지 전구의 색을 바꾸는 횟수의 최솟값을 출력하는 문제이므로 전구들의 묶음을 여러크기로 쪼개 결국 마지막엔 모든 전구의 색이 같아지는 횟수의 최소값을 구하겠다는 접근으로 출발했다.
아래의 그림으로 이어 설명한다.

먼저 인접한 전구의 색이 같을 경우 하나로 묶어서 새로운 bulbs_arr로 선언해주었다.

묶음 사이즈가 1

그 다음 묶음 사이즈가 1일때 전구의 색이 같아지는 최소값을 적어준다.

구간 [1,1]이란 말은 1번전구부터 1번전구까지 색이 같아지는 구간이라는 뜻이고 당연하게도 최소값 비용은 0이다.

묶음 사이즈가2

묶음 사이즈가 2일때이다.

이때는 1번전구부터 2번전구까지의 색을 같아지게하는 비용이 1이다. 식과 같이 구간 [1,1] + [2,2] + 1번전구와 2번전구의 색이 같은지를 검사하고 연산해 구간 [1,2]에서의 최소비용을 구한다.

묶음 사이즈가 3일때

묶음 사이즈가 3일때이다.

구간 [1,3]은 위의 식과 같이 [1,1] + [2,3] + 색_차이_여부 or [1,2] + [3,3] + 색_차이_여부 이렇게 두가지의 경우로 나누어 계산할 수 있다. 

이 경우들 중에 최소비용값을 찾고 저장한다.

묶음 사이즈가 4일때

 

묶음 사이즈가 4일때이다. 각 구간은 3가지의 경우로 나뉘고 그 경우들 중에서 최소비용값을 찾고 저장한다.

묶음 사이즈가 5일때

경우의 수 4가지에 대해서 최소비용을 찾고 저장시킨다.

DP 2처원배열

DP 2차원 배열을 INF값로 초기화시키고 최소비용을 매칭되는 칸에 저장한다.

즉 위의 예시에선 dp[1][5]가 답이 된다.

---

Code

import sys

INF = 99999


def n_size(new_n):
    for i in range(1, new_n + 1):
        if bulbs_tmp_arr[i] == bulbs_tmp_arr[i - 1]:
            new_n -= 1
    return new_n


def make_bulbs_arr():
    for i in range(1, len(bulbs_tmp_arr)):
        if bulbs_tmp_arr[i] != bulbs_tmp_arr[i - 1]:
            bulbs_arr.append(bulbs_tmp_arr[i])
    bulbs_arr.insert(0, 0)


def make_dp(n_arr_size):
    dp = [[INF] * (n_arr_size + 1) for _ in range(n_arr_size + 1)]
    for i in range(1, n_arr_size + 1):
        dp[i][i] = 0
    return dp


def solve(dp, k):
    for size in range(2, k + 1):
        for start in range(1, k + 2 - size):
            end = start + size - 1
            for mid in range(start, end):
                new_value = dp[start][mid] + dp[mid + 1][end]
                if bulbs_arr[start] != bulbs_arr[mid + 1]:
                    new_value += 1
                if dp[start][end] > new_value:
                    dp[start][end] = new_value
    return dp


n, k = map(int, sys.stdin.readline().split())
bulbs_tmp_arr = list(map(int, sys.stdin.readline().split()))
bulbs_tmp_arr.insert(0, 0)
bulbs_arr = []

make_bulbs_arr()
arr_new_n = n_size(n)
bulbs_dp_arr = make_dp(arr_new_n)
asw_dp = solve(bulbs_dp_arr, arr_new_n)
print(asw_dp[1][arr_new_n])