백준 2449 전구

 

dp문제입니다. 처음에 계속 전구 색깔에 집착을 하여 정해진 색으로 맞출려고 했는데 잘 안되었습니다.

 

그런데 사실 무슨 색인지는 중요하지가 않습니다. 그냥 해당 전구의 색으로 다맞추면 상관 없기 때문입니다.

 

dp 배열에 전구의 구간을 (왼쪽이나 오른쪽끝)의 전구색으로 바꾸는데 필요한 최소 횟수를 저장하면 됩니다.

 

즉 dp[i][j] = i~j 구간의 전구를 i색으로 바꾸는데 필요한 최소 횟수입니다. (저는 i로 정했습니다.)

이때 생각 해주셔야 하는 것이 

전체 구간 start - end 에서

             start ~ i / i+1 ~ end 구간으로 나눌 때 start 전구와 i+1 전구의 색을 비교 해야 합니다.

그 이유는 저 구간을 끝내고 돌아왔을 때 둘의 색이 다르다면 한쪽으로 색을 맞춰줘야 하기 때문에 한번의 동작을 더 시행해야 합니다. 만약 둘의 색이 같다면 그럴 필요가 없겠죠. 나머지는 각 구간에 따라 진행을 해주시면 됩니다.

 

아래는 코드입니다.

#include <iostream>
#include <cstring>
#include <algorithm>

#define INF 987654321
using namespace std;

int N, K;
int dp[220][220]; //i,j 구간을 i 색으로 바꾸는데 필요한 횟수
int arr[220];

int sol(int start, int end) {
	

	if (start == end) {
		return 0;
	}

	int &ret = dp[start][end];
	if (ret != -1) return ret;
	ret = INF;
	
	for (int i = start; i < end; i++) {
		int left = sol(start, i);
		int right = sol(i + 1, end);
		int temp;

		if (arr[start] == arr[i + 1]) temp = 0; //양 구간 동일한 색일경우
		else temp = 1;


		ret = min(ret, left + right + temp);

	}
	

	
	return ret;
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(NULL);

	memset(dp, -1, sizeof(dp));
	cin >> N >> K;

	int ans = INF;
	int idx = 0;
	for (int i = 0; i < N; i++) {
		int x; cin >> x;
		if (i == 0)arr[idx++] = x;
		else if(x != arr[idx-1]) arr[idx++] = x;
	}


	cout<<sol(0, idx - 1);


	return 0;
}