boj, 백준) 2449. 전구 ( C / C++)

1. 문제 링크

https://www.acmicpc.net/problem/2449

2449번: 전구

 

2. 문제 개요

최대 K가지의 서로 다른 색을 표현할 수 있는 전구들이 있다.

근접한 전구 중 같은 색이라면 하나의 묶음이라고 보고, 모든 전구의 색이 하나로 같아질 때까지 전구의 색을 바꾸는 횟수의 최솟값을 하나의 정수로 출력하자.

 

 

3. 문제 힌트

   분할정복 방법으로 풀어야 한다.

dp(1, n)을 구간 1에서 n까지의 전구의 색을 바꾸는 횟수의 최솟값이라고 정하고,

 

dp(1, k) + dp(k+1, n)으로 분할하여 최솟값을 찾아보자.

 

4. 문제 풀기

처음 문제를 읽었을 때 K값이 필요 없지 않나?라고 생각은 바로 했지만.. 그래도 색깔을 한번 사용해보자 라고 생각했다.

그래서 생각한 방법이 있는데

dp(왼쪽 구간, 오른쪽 구간, 색깔)로 정의해서 해당 색으로 되어있고, 해당 구간에서의 최솟값을 갖는다.라고 했다.

그래서 구현했는데, 역시나 시간 초과였다. 분할하고 다시 합칠 때 모든 색을 다 brute force로 볼 수밖에 없기 때문에 시간 초과가 났다.

 

그래서 시간을 줄여보려고 좀 더 건드려봤지만, 조금 더 건드린다고 시간이 확 줄 거 같진 않고 반복문을 줄여야 하는데 도저히 답이 생각이 안 나서 다른 분들의 풀이를 조금 참고했다.

 

1가지 힌트를 얻고 다시 풀어봤다.

1가지 힌트는 색깔을 모두 고려할 필요가 없다는 것이다. 그런데 모든 블로그나 풀이들도 마찬가지로 왜 고려할 필요가 없는지는 안 적어놓고 고려할 필요가 없다는 것만 적어놔서 뭔가 조금 아쉬웠다,

 

dp로 구간을 분할하고 합칠 때

가장 왼쪽의 전구의 색을 기준으로 한다.

따라서 구간을 2개로 나누고 다시 1개로 합칠 때 두 구간의 가장 왼쪽 전구의 색깔이 다르면 +1,

아니면 그냥 두 값만 합친다.

 

 

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

int dp_table[201][201];	//left, right, color
int arr[201];
int n, k;

//색은 left의 색으로 다 만들었다고 가정
int dp(int left, int right)
{
	if (left == right)
		return dp_table[left][right] = 0;

	int &cache = dp_table[left][right];
	if (cache != -1)	return dp_table[left][right];

	int ans = 987654321;
	for (int i = 0; left + i + 1 <= right; ++i) {
		int weight = 0;
		if (arr[left + i + 1] != arr[left])	weight = 1;
		ans = min(ans, dp(left, left + i) + dp(left + i + 1, right) + weight);
	}
	return cache = ans;
}

int main()
{
	scanf("%d %d", &n, &k);

	for (int i = 1; i <= n; ++i)
		scanf("%d", &arr[i]);

	memset(dp_table, -1, sizeof(dp_table));

	printf("%d", dp(1,n));
	return 0;
}

6. 결과 사진