백준 11066, 파일 합치기

이것도 컨셉을 보고 구현했다. 아무리 생각해도 부분으로 나눈게 최적해가 왜 되는지 이해가 안간다.

문제

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

풀이

처음에는 이진 트리로 그리고 문제 풀이에 접근하거나 배낭문제 비슷하게 구현하지 않을까 생각은 했는데 막상 정답을 봐도 잘 이해가 가지 않았다.

부분합으로 하는 경우에 소설의 장을 마구 섞었을때는 트리의 모양이 바뀔텐데 그래도 같은 최적값이 나오는 이유를 잘 모르겠다.

관련 문제를 많이 풀어봐야 할 것 같다.

아 dp 최적화를 쓰면 n^2로도 풀 수 있다고 한다.

실수

• 컨셉을 이해 못함
• 초기화 안함

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>

using namespace std;

vector<vector<long long int>> dp(550, vector <long long int > (550, 2e9));
vector<long long int> sum(550, 0);

int main() {

	int t, k;
	long long int temp;

	scanf("%d", &t);

	for (int i = 0; i < t; i++) {

		scanf("%d", &k);

		for (int j = 1; j <= k; j++) {

			scanf("%lld", &temp);

			dp[j] = vector <long long int >(550, 2e9);

			dp[j][j] = 0;

			sum[j] = sum[j - 1] + temp;

		}

		

		for (int diff = 1; diff <= k - 1; diff++) {

			for (int a = 1; a <= k; a++) {

				for (int b = a + 1; b <= k; b++) {

					if (b - a == diff) {

						for (int c = a; c < b; c++) {

							dp[a][b] = min(dp[a][b], dp[a][c] + dp[c + 1][b] + sum[b] - sum[a - 1]);

						}

					}

				}

			}

		}

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

	}

	return 0;


}