문제
풀이
동적계획법 문제이다. DP[i][j] = i부터 j까지의 합치는데 필요한 최소 비용 으로 정의한다.
for문 제일 바깥쪽 i는 페이지를 합치는 사이즈 - 1 을 의미한다. 즉, i = 1이면 두개를 서로 합치는 것이다. for문 중간에 위치한 j는 합치는 것을 진행하는 시작점이다.
for문 제일 안쪽 k는 중간에 분리하는 지점을 의미한다.
예를 들어 테스트 케이스 40 30 30 50 이 있고 i = 3일 때, 40/30 30 50(j=1, k=1), 40 30/30 50(j=1, k=2), 40 30 30/50(j=1, k=3)으로 분리하여 최솟값을 찾아서 저장해 놓는 것이다.
또, i = 2 일 때, 40/30 30(j=1, k=1), 40 30/30(j=1, k=2), 30/30 50(j=2, k=2), 30 30/50(j=2, k=3)으로 분리하여 최솟값을 찾아내 저장한다.
이런식으로 i=1, j=1, k=j일 때 부터 차근차근 다 저장하여 원하는 값인 DP[1][M]을 구하면 되는 문제이다.
참고로 climits STL을 이용하여, int_min(= -214748347-1), int_max(= 214748347)를 이용할 수 있다.
소스 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main(){
int N;
scanf("%d", &N);
while(N--){
int M;
scanf("%d", &M);
vector<int> sum(M+1);
for(int i = 1; i<=M; i++){
int input;
scanf("%d", &input);
sum[i] = sum[i-1] + input;
}
vector<vector <int>> dp(M+1, vector<int>(M+1));
for(int i = 1; i<=M; i++){
for(int j = 1; j<=M-i; j++){
dp[j][i+j] = INT_MAX;
for(int k = j;k<i+j;k++){
dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j] + sum[i+j] - sum[j-1]);
}
}
}
printf("%d\n", dp[1][M]);
}
}
