[BAEKJOON] 11066번 : 파일 합치기*

문 제

 

소 스  코 드

#include <iostream>
#include <algorithm>
constexpr int MAX{ 0x7fff'ffff };


void SearchLowCost();

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);


	int T;
	std::cin >> T;

	for (int i = 0; i < T; ++i) SearchLowCost();

	return 0;
}


void SearchLowCost() {
	int K;

	std::cin >> K;
	int *sum		{ new int[K + 1] };
	int data;

	std::fill_n(sum, K + 1, 0);

	for (int i = 1; i <= K; ++i) {
		std::cin >> data;
		sum[i] = sum[i - 1] + data;
	}
	
	int **dp		{ new int*[K + 1] };
	for (int i = 0; i <= K; ++i) {
		dp[i] = { new int[K + 1] };
		std::fill_n(dp[i], K + 1, 0);
	}
	

	for (int i = 1; i < K; ++i) {
		for (int x = 1; x + i <= K; ++x) {
			int y = x + i;
			dp[x][y] = MAX;

			for (int m = x; m < y; ++m) {
				dp[x][y] = std::min(dp[x][y], dp[x][m] + dp[m + 1][y] + sum[y] - sum[x - 1]);
			}
		}
	}

	std::cout << dp[1][K] << '\n';

	for (int i = 0; i < K + 1; ++i) delete[] dp[i];
	delete[] dp;
	delete[] sum;
}

 

풀 이

 

• 연쇄행렬 최소곱셈

문제에 "소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다."라는 말을 통하여 두 개를 선택할 경우 옆에 있어야 하는 것을 알 수 있다.

이와 유사한 방법이 연쇄행렬 최소곱셈이다.

dp[i][j] : i번째 ~ j번째 까지 합치는데 드는 최소한의 비용.

그러므로, min(dp[i][k] + dp[k+1][j] + novel의 i ~ j까지의 합, dp[i][j]) 인 것을 알 수 있다.

 

 

 

 

출 력 값

 

 

문 제  출 처

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

11066번: 파일 합치기