백준 2449 전구 C++ - DP

전구를 하나 뒤집으면 그 좌우로 같은 숫자가 연결되는 곳까지 같이 뒤집어진다.

최소 횟수로 모두 다 같은 불빛으로 만드려면 몇 번이 필요할까?

 

우선 불빛의 종류가 20가지이고 N이 200개 까지 있으므로

Brute force 로 풀기에는 경우의 수가 너무 많다. 

 

이럴 때는 역시 Dynamic programming 으로 푸는 것이 제맛!

 

DP 는 항상 다음 세 가지를 유의하자.

1. 배열 정의

2. 점화식

3. 초기값

 

먼저 배열을 정의해보자.

나는 dp[i][j] 를 i 에서 j 까지 전구를 같게 만드는데 필요한 최소 횟수로 정의했다.

이럴 경우 dp[1][N] 이 최종 답이 될 것이며, 1~N 사이의 값을 넣어서 최소 값을 구해주면 될 것이다.

 

점화식을 구해보자.

초기값은 i 와 j 가 같은 경우 0 과 

i와 j가 바로 옆에 있는 경우, 색이 다르면 1 같으면 0 번 필요하다.

 

dp[1][1] 은 이미 같으므로 0번 필요하다.

dp[1][2] 는 1번과 2번이 다를 경우 1번, 같을 경우 0번이 필요하다.

dp[1][3] 은 min ( dp[1][2] + (1번과 3번이 다를 경우 1, 같은 경우 0) , dp[2][3] + (1번과 3번이 다를 경우1, 같은 경우 0))

 

왜 전구의 색이 같은지 다른지 판단할 때 2번과 3번으로 하지 않고 1번과 3번으로 하느냐?

사실 상관 없다. 다른 영역에 해당하는 애들만 비교할 수 있으면 된다.

 

dp[1][4] = min(dp[1][1]+dp[2][4]+(1!=2), dp[1][2]+dp[3][4] + (2 != 3) , dp [1][3] + dp[4][4] + (3!=4)) 

모든 경우의 수를 고려해야 한다.

 

즉 1~N 까지 중 1~i, i+1 ~ N  두 영역으로 자를건데, 1~i 영역에서도 가장 작은 값을 찾기위해 1~j, j+1~ i 식으로

계속 잘라서 생각하는 방식이다.

 

재귀를 사용하면 top-down 방식으로 1~N 을 넣고 1~1부터 계산하는 방식이고,

for 문을 사용하면 bottom-up 방식으로 dp[1][1] dp[2][2] 부터 계산해서 차례대로 쌓아가는 방식이다.

 

재귀 방식

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


int N, K;

int bulb[201];
int dp[201][201];

int query(int start, int end) {
	//같은 번호면 무조건 0
	if (start == end) return 0;
	//이미 계산했다면
	if (dp[start][end]) return dp[start][end];
	//바로 옆에 전구고 색 다르면 1 아니면 0
	if (start - 1 == end) return bulb[start] != bulb[end];

	//계산한적 없다면 계산
	int ret = 987654321;
	for (int i = start; i < end; i++) {
		// D[1][N] = min ( D11+D2N+ 같은지, D12+D3N + 같은지,..,D1N-1+DNN+같은지)
		// 왜 같은지를 start end 로만 판단? -> i 로 해도 상관 x 
		ret = min(ret, query(start, i) + query(i + 1, end) + (bulb[i] != bulb[end]));
	}
	return dp[start][end] = ret;
}

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d", bulb + i);
	}

	printf("%d\n", query(1,N));
}

반복문 방식

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

int N, K;
int bulb[201];
int dp[201][201];

int main() {
	scanf("%d %d", &N, &K);
	for (int i = 1; i <= N; i++) {
		scanf("%d", bulb + i);
	}

	for (int interval= 1; interval < N; interval++) {
		for (int i = 1; i < N - interval+1; i++) {
			int s = i;
			int e = i + interval;

			int tmp = 987654321;
			for (int j = s; j < e; j++) {
				tmp = min(tmp, dp[s][j] + dp[j + 1][e] + (bulb[s] != bulb[e]));
			}
			dp[s][e] = tmp;
		}
	}

	printf("%d\n", dp[1][N]);
}