백준 11066 파일 합치기

문제 : https://www.acmicpc.net/problem/11066

 

서론

계산할 수 있는 모든 경우의 수를 재귀+메모이제이션으로 풀려고 했으나 메모이제이션을 어떻게 해야할지 전혀 떠오르지 않았다. 그래서 아래 블로그의 2번 풀이를 참고했다.

참고한 풀이와 90% 유사한데 유사하지 않은 부분은 for문의 추가로 시간복잡도가 좋지않다.

https://js1jj2sk3.tistory.com/3

 

풀이

예 : 40 30 30 50

 

구간 1~4는

40 / 30 30 50

40 30 / 30 50

등의 여러가지 방법으로 2분할이 가능함

구간 1~4에서 분할된 방법 중 하나인 40 / 30 30 50의 오른쪽 30 30 50은

30 / 30 50

30 30 / 50

으로 다시 분할이 가능함

분할된 30 / 30 50의 오른쪽 30 50은
다시 30 / 50으로 분할이 가능함
즉 분할된것은 또다시 분할 될 수 있고 더이상 분할 할 수 없을때까지 분할이 반복됨 -> 재귀함수 사용
이때 분할된 결과는 항상 왼쪽과 오른쪽이 나오는데 왼쪽과 오른쪽을 더해주면 두 부분을 합쳐주는 비용이 됨 -> DP 사용
또한 각 구간(1~4, 2~4 등)은 여러가지 방법으로 분할이 가능하므로 분할하는 방법에 따라 비용이 다르게 나올 수 있음, 비용들 중 최소값을 결과로 가져옴
1~4의 오른쪽 구간이 2~4이면 1~4의 최소비용은 2~4의 최소비용을 이용하게 되고 이것이 분할될 수록 반복됨

 

전체 코드

// C++

#pragma warning(disable : 4996)

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

using namespace std;

#define MAX_SIZE 501

int dp[MAX_SIZE][MAX_SIZE];
int k;

int recursive(int start, int end) {
	//cout << start << " " << end << endl;
	if (start == end) return 0;
	if (start + 1 == end) return dp[start][end] = dp[start][start] + dp[end][end];
	// 같은 구간 반복 탐색방지, 이 코드 없을시 시간초과
	if (dp[start][end] != 0x3f3f3f3f) return dp[start][end];

	for (int mid = start; mid < end; mid++) {
		int left = recursive(start, mid);
		int right = recursive(mid+1, end);
		dp[start][end] = min(dp[start][end], left + right);
	}
	// 왼쪽과 오른쪽을 합친 비용 + 각 구간의 비용이 만들어질 수 있었던 기저비용
	for (int i = start; i <= end; i++) {
		dp[start][end] += dp[i][i];
	}
	return dp[start][end];
}

int main() {
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		memset(dp, 0x3f, sizeof(dp));
		scanf("%d", &k);
		for (int j = 1; j <= k; j++) {
			scanf("%d", &dp[j][j]);
		}
		printf("%d\n", recursive(1, k));
	}
}