[BOJ 2449] 전구

문제 출처 : https://www.acmicpc.net/problem/2449

 

문제 풀이 :

 

DP 문제입니다.

 

cache[L][R] : L번째 전구부터 R번째 전구까지 통일 시키는데 색을 바꾼 최소횟수

 

양쪽 구간의 색을 통일 시킬때 변수를 하나 두시고 양쪽 구간의 시작 색깔이 같다면 바꾸는 비용을 0으로, 다르다면 바꾸는 비용을 1로 계산하여 쌓아가시면 됩니다.

 

 

	#include<iostream>
	#include<algorithm>
	using namespace std;
	int n, k, arr[200], cache[200][200];
	int func(int l, int r) {
	if (l >= r)return 0;
	int& ret = cache[l][r];
	if (ret)return ret;
	ret = 1e9;
	for (int i = l; i < r; i++) {
	int p = arr[l] == arr[i+1] ? 0 : 1;
	ret = min(ret, func(l, i) + func(i + 1, r) + p);
	}
	return ret;
	}
	int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n; i++)cin >> arr[i];
	cout << func(0, n - 1);
	}

view raw 2449.cpp hosted with ❤ by GitHub