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

1. 문제

2. 예제 입출력

3. 문제 해설

다이나믹 프로그래밍 문제이다. 나는 한 번 최소의 값을 구하는 과정을 생각해보았다. 

내가 풀어본 대부분의 dp문제 중 이 문제는 dp[x][y]를 x번째에서 y번째까지의 파일 합치기의 최소값을 기억해두는 문제였다. 

(백준-전구)에서 사용한 dp배열과 비슷하다. 

 

대부분 이렇게 x ~ y에서의 최소 값을 dp배열에 저장하면 중간에 k라는 구간을 두어 for문을 반복하며 최소 값을 찾아내는 형태로 많이 나온다. 

 

이 문제 또한 동일했다. 

 

dp문제 정의

1. dp배열 정의 : dp[x][y] : x번째 파일에서 y번째 파일까지 합치기의 최소 값
2. 점화식 : dp[i][i+j] = min(dp[i][j] , dp[i][k] + dp[k+1][i+j]) k 는 i부터 i+j-1까지 
3. 초기 값 : 바로 옆에 붙어있는 경우 두 수의 합이 최소의 파일 합치기 값이다. 

---

대각선으로 채워가는 dp배열

대각선으로 채워가는 dp배열이 필요하다. 이 dp풀이는 마치 행렬곱셈의 최소값을 구하는 배열과 비슷한 방향으로 구해야한다.

 

예제 중 첫번째를 예시로 들면 다음과 같다. 

4

40 30 30 50

dp배열은 초기에 다음과 같이 채워질 것이다. 

dp[1][2] , dp[2][3], dp[3][4]는 바로 옆의 수를 의미하므로 다음과 같이 바로 옆의 수와의 합에 해당한다.

0	70
	0	60
		0	80
			0

작게 표를 나눠보면 저 주황색 칸을 구하기 위해서는 주황색 칸이 dp[1][3]에 해당하므로 dp[1][1] , dp[2][3] , dp[1][2] , dp[3][3]이 필요하므로 자신의 이전 열과 자신의 이전 행에 존재하는 dp정보들이 필요하다. 따라서 대각선 아래 방향으로 dp배열을 구해줘야한다.

 

주황색 칸들을 구해주기 위해서는 다음과 같은 정보들이 필요하다. 

 

따라서 대각선 아래로 dp배열 구성을 해주었고 중간에 k라는 변수를 두어 시작점부터 끝점까지 이동하게 해주었다. 

 

대각선 이동 인덱스

for(int j = 2; j < K; j++) {
	for(int i=1; i <= K; i++) {
    	if(i + j <= K) {
        	// 로직
            for(int k = i; k < i+j; k++) {
            	// 시작점과 끝점 사이의 경유점을 의미한다.
                //로직
            }
        }
    }
}

---

4. 코드

#pragma warning (disable : 4996)

#include <cstdio>
#include <cstring>
#include <algorithm>
#define MAX 502
#define INF 0x3f3f3f3f
using namespace std;
int T;
int K;
int files[MAX];
int sums[MAX];
int dp[MAX][MAX]; // i ~j의 최솟 값 
void input() {
	memset(dp, 0, sizeof(dp));
	memset(sums, 0, sizeof(sums));
	scanf("%d", &K);
	for (int i = 1; i <= K; i++) {
		scanf("%d", &files[i]);
		sums[i] = sums[i - 1] + files[i];// 누적합 배열 만들어준다.
	}
}

void sol() {
	
	for (int i = 1; i <= K; i++) {
		dp[i][i] = 0;
		dp[i][i + 1] = files[i] + files[i + 1];
	}
	int temp = 1;
	for (int j = 2; j < K; j++) {
		for (int i = 1; i <= K; i++) {
			if (i + j <= K) {
				int temp = 0;
				dp[i][i+j] = INF;
				for (int k = i; k < i+j; k++) {
					dp[i][i+j] = min(dp[i][i+j], dp[i][k] + dp[k + 1][i+j]);
				}
				dp[i][i + j] += sums[i+j] - sums[i-1];
			}
		}
	}
	
}
int main() {
	scanf("%d", &T);
	for (int i = 0; i < T; i++) {
		input();
		sol();

		printf("%d\n", dp[1][K]);
	}
	return 0;
}