BOJ 2449 전구

문제 링크입니다.

문제 요약

$N$개의 전구가 일렬로 있습니다. 행동 한 번에 색이 같은 연속한 전구들의 색을 바꿀 수 있습니다. 모든 전구를 같은 색으로 만드는 데 필요한 최소 행동 수를 구하세요.

풀이

DP를 하고 싶게 생겼습니다. $N$ 제한은 꽤 작은 편이라, ${\cal O}(N^3)$ 정도의 풀이까지는 고민해 볼만 합니다. 보통은 ${\cal O}(N)$만에 전파 가능한 ${\cal O}(N^2)$ 크기의 DP가 많습니다. 특히 이런 구간을 합치는 종류의 DP 같은 경우에는, $d[l][r] :=$ 구간 $[l,r]$을 조건을 만족하도록 만드는 데 필요한 최소 행동 수 같은 걸로 정의하면 대충 맞습니다.

그러니 그렇게 정의하고 전파 방법을 생각해 봅시다. 각 구간을 어느 색으로 통일할 지가 정해져 있다면 $d[l][r] = \underset{i}{\min}\ d[l][i]+d[i+1][r]+(C_l = C_r)$ 같은 느낌으로 쉽게 ${\cal O}(N^3)$에 해결할 수 있을 텐데요.

Claim: 왼쪽 색깔만 보면 됨

여기서 다음의 사실을 증명할 수 있습니다: $C_l = A[l], C_r = A[i+1]$로 두면 위의 DP 식이 실제로 맞습니다. 즉, 각 구간을 가장 왼쪽의 색으로 통일하는 경우만 고려해도 충분합니다. 이거 좀 비자명한 내용인 거 같은데, 설명 있는 글이 잘 없더라고요…

가장 왼쪽 전구의 색을 바꾸지 않는 최적해가 존재함을 관찰합시다. 맨 왼쪽 전구의 색을 바꾼다고 해서 양쪽 구간을 동시에 합쳐지는 이득을 볼 수 없기 때문입니다. 이러한 논의는 일반적인 모든 부분배열에 대해 성립하기 때문에, 어떤 부분배열을 하나의 색으로 통일하는 최소 횟수의 방법 중, 그 부분배열의 가장 왼쪽 전구의 색으로 통일하는 방법은 반드시 존재합니다. 그래서 우리는 DP 식의 의미를 기존의 임의의 색으로 통일하는 최소 횟수에서 구간 내 가장 왼쪽 전구의 색으로 통일하는 최소 횟수로 바꿀 수 있습니다. 이래도 값이 똑같아요.

이제 DP 식은 구간을 두 소구간으로 분할하고 각각을 하나의 색으로 통일한 뒤, 오른쪽 구간을 왼쪽 구간의 색으로 통일시키는 데 필요한 행동 횟수를 구하고 있습니다. 두 구간을 합칠 때의 색이 각각 $A_l$과 $A_{i+1}$로 통일되기 때문에 위의 식에서 왼쪽 전구의 색만 확인해 보아도 괜찮게 됩니다.

해서 총 시간 복잡도는 처음에 제시했던 ${\cal O}(N^3)$이 됩니다.

코드

#include<bits/stdc++.h>
using namespace std;
int a[210], d[210][210];

int dp(int l, int r){
	if(l > r) return 0;
	int& ret = d[l][r];
	if(ret != -1) return ret;
	if(l == r) return ret = 0;
	ret = 1234;
	for(int i = l; i < r; i++){
		ret = min(ret, dp(l, i)+dp(i+1, r)+(a[l] != a[i+1]));
	}
	return ret;
}

int main(){
	cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);
	memset(d, -1, sizeof(d));
	int n, k; cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	cout << dp(1, n);
}