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

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

11066번: 파일 합치기

 

DP 문제다.

 

파일을 합치는 데는 두 파일의 무게의 합 만큼의 비용이 들고, 이 비용을 최소화 하는 문제다.

파일을 합칠 때는 연속한 두 개를 선택하여 합칠 수 있다.

 

처음 생각한 방법은 1차원 배열을 이용해 최소의 비용을 찾아나가는 것이다.

1번 파일부터 n-1번 파일까지 고려된 최소 비용에 n번 파일을 합치는 비용을 고려했다.

1 2 3 4 라는 파일이 있는 경우 3까지 계산이 됐다고 하면

4를 포함하는 최소 비용을 계산할 때는 (1,2,3) (4) 를 계산하는 방법과 (1, 2) (3, 4)를 계산하는 방법이 있다.

그러나 이렇게 계산하는 경우 (1 (2) (3, 4)) 계산을 할 수 없기에 반례가 존재했다.

 

따라서 2차원 배열을 이용했고, n-k번 파일부터 n번 파일까지 포함하는 최소비용을 계산했다.

(엑셀에 계산 했는데 엑셀을 날렸다... 블로그 쓸 거 생각해서 캡쳐라도 해둘 걸... .·´¯`(>▂<)´¯`·. )

 

2차원 배열에 각각의 경우의 수를 구해보니 아래와 같은 점화식을 얻었다.

dp[i][j] = min(dp[i][j], tmp + dp[k][j] + dp[i - k][j - k])

 

#include <iostream>
#include <climits>
using namespace std;

int t, n;
int arr[501];
int dp[501][501];

int main() {
    
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);    cout.tie(NULL);
    
	cin >> t;
	while (t--) {
		cin >> n;

		for (int i = 2; i <= n; i++)
			for (int j = 1; j <= n; j++) dp[i][j] = INT_MAX;

		for (int i = 1; i <= n; i++) {
			cin >> dp[0][i];
			arr[i] = arr[i - 1] + dp[0][i];
		}
		for (int i = 2; i <= n; i++) dp[2][i] = dp[0][i] + dp[0][i - 1];

		for (int i = 3; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (j >= i) {
					int tmp = arr[j] - arr[j - i];

					for (int k = i - 1; k > 0; k--) {
						dp[i][j] = min(dp[i][j], tmp + dp[k][j] + dp[i - k][j - k]);
					}
				}
			}
		}
		cout << dp[n][n] << "\n";
	}

}