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

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

11066번: 파일 합치기

꽤 어려운 DP 문제였습니다.

문제 조건

출력 예시

접근이 어려워 https://js1jj2sk3.tistory.com/search/11066 해당 블로그에서 접근 방법을 알았습니다.

 

먼저 고려해야할 것은 인접된 파일들만 겹칠 수 있다는 점입니다. 따라서 정렬을 한 뒤 합치는등, 배열을 섞으면 안됩니다. 따라서 메모리제이션을 통해서 DP를 풀어나가야 한다는 것입니다.

저는 Dp[i][j]인 2차원 배열을 설정했습니다. Dp[i][j]의 뜻은 i부터 j까지 파일을 합치는 것의 최솟값을 의미합니다.

 

Dp의 접근 방법은 두 그룹으로 나누는 것입니다.

예를 들어 40 30 30 50 이라고 한다면, {40} / {30, 30, 50}으로 나눈 뒤 계산을 하거나, {40, 30} / {30, 50}으로 나누어 계산하는 등, 2개의 그룹으로 나누어서 계산을 하면 됩니다.

 

따라서 Dp[i][j]의 점화식은 min(Dp[i][j], Dp[i][k] + Dp[k+1][j] + sum[j] - sum[i-1])가 되겠습니다.

이때 k는 i 이상 j미만인 수이며, sum[j] 배열은 1번부터 j번까지의 파일의 총 합이 됩니다.

 

 

자세한 것은 코드를 참고해주세요!

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstring>
#include <vector>
#include <iostream>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstdio>
#include <string>
#include <deque>

using namespace std;

int test_case;
int dp[501][501];
int sum[501];
int cost[501];
int K;

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> test_case;
	for (int k = 0; k < test_case; k++) {
		cin >> K;
		for (int i = 1; i <= K; i++) {
			cin >> cost[i];
			sum[i] = sum[i - 1] + cost[i];
		}
		for (int i = 1; i < K; i++) {
			for (int tx = 1; tx + i <= K; tx++) {
				int ty = tx + i;
				dp[tx][ty] = 987654321;
				for (int mid = tx; mid < ty; mid++) {
					dp[tx][ty] = min(dp[tx][ty], dp[tx][mid] + dp[mid + 1][ty] + sum[ty] - sum[tx - 1]);
				}
			}
		}
		cout << dp[1][K] << "\n";
	}
	return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!