[백준] 11066-파일 합치기(C++)

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

11066번: 파일 합치기

어려웠습니다.

처음에 문제의 조건을 잘못 읽고 순서가 바뀌어도 되는줄 알고 그리디적인 관점으로 생각했다가 틀렸습니다. 

 

dp적인 관점으로 생각해야하는 문제입니다. 예시인 40 30 30 50을 봅시다. 

 

아래의 표는 i부터 j까지의 합의 최소값을 나타내는 표입니다. 

	1	2	3	4
1	0	70	60 + 100(70+30) =160	70 + 80 + 150 =300
2		0	60	60 + 110(80+30) =170
3			0	80
4				0

 

즉 각각의 값들은 min(기존값,  좌와 아래로 내려간 값들의 합 + 대각선 횟수만큼 sum 값의 차이) 입니다. 

 

3중 포문을 통해서 구현해야 합니다.

 

코드는 먼저 보여드리겠습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
//(int)2e9;
int sum[501] = { 0 };
int arr[501] = { 0, };
int dp[501][501] = { 0, };
int t = 0, k = 0;
int result = 0;
int main() {
	cin >> t;

	while (t--) {
		cin >> k;
		result = 0;
		for (int i = 1; i <= k; i++) {
			cin >> arr[i];
			sum[i] = sum[i - 1] + arr[i]; 
		}
		
		for (int i = 1; i < k ; i++) { // 1부터~ k-1 까지 반복 대각선의 개수
			for (int j = 1; j + i <= k; j++) { //  행을 나타낼 j변수   
				int v = j + i;    //  열값을 표현 
				dp[j][v] = (int)2e9;  // 2*10^9

				for (int u = j; u < j + i; u++) // 점 기준으로 좌와 하로 내려가면서 값 비교하기 위한 반복분 j부터 i번 반복
					dp[j][v] = min(dp[j][v], dp[j][u] + dp[u + 1][v] + sum[j + i] - sum[j - 1]);
					//지정된 위치 값은 -> min(기존값,  좌와 아래로 내려간 값들의 합 + i만큼의 sum 값의 차이)
			}

		}
		for (int i = 1; i <= k; i++) {
			for (int j = 1; j <= k; j++)
				cout << dp[i][j] << ' ';
			cout << endl;
		}
		cout << dp[1][k] << endl;

	}
	return 0;
}

 

삼중 포문을 통해서 구현하게 됩니다.

• 1. 첫번째 포문은 대각선의 수만큼 반복되게
• 2. 두번째 포문은 각 대각선마다 해당하는 개수만큼 반복되게 (i+j <= k)
• 3. 세번째 포문은 각 점마다 아래와 왼쪽으로 한칸씩 이동하며 반복되도록 

 

다음은 top-down 방식인 재귀를 통해서 구현한 코드입니다. 

점화식만 구하면 훨씬 직관적이고 빠르게 구현이 가능하지만 효율측면에서는 down-top 방식보다 느리다는 단점도 있습니다. 

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


int t, k;
int arr[501] = { 0, };
int dp[501][501] = { 0, };

int solved(int s, int e) {
	if (s == e) return 0;
	else if (s + 1 == e) return arr[e] - arr[e - 2];

	int &ret = dp[s][e];
	if (ret != -1)
		return ret;
	ret = 1000000000;
	for (int i = s; i <= e; i++) {
		ret = min(ret, solved(s, i) + solved(i + 1, e) + arr[e] - arr[s-1]);
	}
	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> t;
	while (t--) {
		memset(dp, -1, sizeof(dp));
		cin >> k;
		for (int i = 1; i <= k; i++) {
			cin >> arr[i];
			arr[i] = arr[i] + arr[i - 1];
		}

		cout << solved(1,k) << "\n";

	}


	

	return 0;
}

 

 

아래 문제를 풀어보면서 복습해봅시다.

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

11049번: 행렬 곱셈 순서