주의해야 하는 부분
1) 소설의 각 챕터이므로 무조건 인접한 것끼리 묶어야 한다.
"이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고," (문제 본문 두 번째 줄)
2) 규칙상 마지막 연산은 전체합을 더해야 한다.
"최종적으로는 하나의 파일로 합친다." (문제 본문 세 번째 줄)
이전 단계들의 연산 과정에 상관없이 최종적으로 파일을 합치기 전 발생되는 cost는 전체 파일의 cost합과 동일하다.
Ex)
1번 예제에서 40, 30, 30, 50 순서대로 파일이 있을 때 전체 비용 계산은 60 + 90 + 150 으로 계산되는데,
마지막 150이라는 값의 경우 60짜리 서브파일과 90짜리 서브파일을 더한 값이기도 하지만,
파일을 합치기 위한 마지막 연산이므로 앞에서 어떤 순서로, 어떤 파일끼리 더했던,
결국엔 1번째 파일 부터 4번째 파일 사이의 모든 파일 cost를 합친 비용(=전체합)이 되기 때문.
접근 방식
총 파일이 4개라고 하면 파일이 합쳐지는 경우의 수는
( (1, 2) (3, 4) ) , ( ( 1, (2, 3) ), 4), .....등등등 여러가지방법이 나오게 된다.
이를 하나하나 해보기에는 너무나도 많은 겹치는 연산들이 있을것이다.
그렇다면 이 겹치는 연산을 줄이기 위해서는 동적계획법 + 누적합을 이용하는게 적절해 보인다.
ex)
1. Files = {a, b, c}(K == 3)라면 {a, b} / c 의 경우와 a / {b, c}의 경우로 나뉜다.
2. 길이 내에서 2개씩 묶어 그 위치를 이동하면서 최소값을 찾아낸다.
즉, DP[1][3](K == 3)을 구할 때 DP[1][2] + DP[3][3]과 DP[1][1] + DP[2][3]중 최소값을 구하면 된다.
이를 점화식으로 만들어 보자면 다음과 같다.
DP[start][end] = DP[start][mid] + DP[mid+1][end] + (files[end] - files[start-1])
*( files[end] - files[start-1] ) : start ~ end 사이의 부분합.
>꿀팁<
1. 이 부분합 계산 때문에 처음 cost값 저장 시에 누적합으로 저장하면 편함.
2. files[start-1]에서 start-1 인덱스 값 때문에 누적합 배열의 시작 index를 0으로 잡으면 머리아픔. 1로 시작하면 편함.
구현
3중 for문으로 구현
1번째 for문 : gap (몇 개씩 묶어서 계산할 범위를 결정할 것인지를 gap 값으로 설정)
2번째 for문 : start
3번째 for문 : mid -> start <=mid < end ( mid < end인 이유는 mid+1로 자르기 때문 )
import java.io.*;
import java.util.*;
public class Main {
static int T;
public static void main(String[] args) throws Exception {
Scanner sc = new Scanner(System.in);
T = sc.nextInt();
for(int t = 0; t<T; t++) {
int files[];
int K = sc.nextInt();
files = new int[K+1];
int dp[][];
dp = new int[K+1][K+1];
files[1] = sc.nextInt();
for(int i=2; i<=K; i++) {
int tmp = sc.nextInt();
files[i] = tmp+files[i-1];
}
for(int gap=1; gap<K; gap++) {
for(int start = 1; start+gap <= K; start++) {
int end = start + gap;
dp[start][end] = Integer.MAX_VALUE;
for(int mid = start; mid<end ;mid++) {
dp[start][end] = Math.min(dp[start][end],dp[start][mid]+dp[mid+1][end]+files[end]-files[start-1]);
}
}
}
System.out.println(dp[1][K]);
}
}
}