최대 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
1 1 2 3 3 3 2 2 1 1
출력 예시
2
풀이
브루트포스로 접근한다고 치면, 20^200개의 경우의 수를 전부 테스트해보아야 한다. 즉 이 경우는 바로 DP를 떠올리는 게 좋다.
DP를 사용하기 전, 우리는 위에 주어진 전구 리스트를 최대한 간소화할 수 있다. 같은 색의 인접한 전구는 모두 한 번에 바뀌므로, 이를 숫자 하나로 표현 가능하기 때문이다. 예시의 경우
1 1 2 3 3 3 2 2 1 1 -> 1 2 3 2 1
로 변환된다.
이제 DP를 초기화해보자. 길이가 1인 경우, 즉 자기 자신인 경우는 아무런 변화가 필요 없고(0), 길이가 2인 경우(인접한 경우)는 앞서 중복을 전부 제거했으므로 무조건 한 번의 변화가 필요하다.
다음은 DP를 업데이트해야한다. 간격이 i라고 가정할 때, DP[j][j+i]는 (j , j+i) 사이의 값 k에 대하여 다음과 같이 업데이트된다고 가정하자.
즉 j부터 k까지의 최소 변환 개수와 k+1부터 j+i까지의 최소 변환 개수의 합을 모든 k에 대해서 따져본 뒤, 이들 중 최솟값이 j부터 j+i까지의 최소 변환 개수가 될 것이다. 그런데 잠깐 생각해 볼 필요가 있다. DP[j][k]를 통해 최종적으로 통합된 전구 색과, DP[k+1][j+i]를 통해 최종적으로 통합된 전구 색은 같을 수도, 다를 수도 있다. 같다면 굳이 추가적인 변환이 필요 없으므로 0을, 그렇지 않다면 한 번의 변환 과정이 더 필요하므로 1을 더해주어야 한다. 그리고 그 값은 전구의 양 끝값, 즉 bulb[j]와 bulb[j+i]을 비교해줌으로써 판별할 수 있다. 이를 통해 최종적으로 다음과 같은 식이 생성된다.
이 과정을 모든 i와 j를 적용하여 구해 주면 DP[0][-1] 값이 최종적으로 우리가 구하고자 하는 최솟값이 된다.
풀이 코드
MAX = float('inf')
def simplify(lst) :
result = [lst[0]]
for num in lst :
if result[-1] != num :
result.append(num)
return result
_, _ = map(int, input().split())
bulb_list = list(map(int, input().split()))
bulb_list = simplify(bulb_list)
N = len(bulb_list)
dp = [[MAX]*N for _ in range(N)]
for i in range(N) :
dp[i][i] = 0
if i == N-1 :
break
dp[i][i+1] = 1
for i in range(2, N) :
for j in range(N-i) :
bulb_diff = 0 if bulb_list[j] == bulb_list[j+i] else 1
for k in range(j, j+i) :
dp[j][j+i] = min(dp[j][j+i], dp[j][k] + dp[k+1][j+i] + bulb_diff)
print(dp[0][-1])
