시간을 정말 많이 써서 고민했던 문제이다. 결국 풀이를 보고 해답을 얻었다 ㅠㅜ..
풀기 위해 고민해야 할 부분을 정리해보자.
DP 변수 설정
이렇게 기본 소스가 되는 novel 변수를 합쳐서 하나의 파일을 만드는 문제는 idx가 줄어드므로 시작위치, 끝 위치를 DP 변수로 설정하면 된다.
즉, DP[start][end] = start~end idx까지의 파일합치기 비용
점화식 찾기
DP 변수를 설정했으면 실제 변수 대입을 통해 규칙을 찾고 그 규칙으로 부터 점화식을 세우자.
DP를 사용하기 위해서는 합치는 길이가 작은 것 부터 점점 키워가면 된다.
len==1
len==2
len ==3
파일을 합치는 비용은 각 인덱스의 값을 모두 합친 부분합임을 포인트로 찾아야 한다.
len==len
최종 코드
import java.util.*;
public class Main {
public static void main(String[] args) {
// 여기에 코드를 작성해주세요.
Scanner sc = new Scanner(System.in);
int T = Integer.parseInt(sc.nextLine());
for (int t = 0; t < T; t++) {
int n = Integer.parseInt(sc.nextLine());
String[] inp = sc.nextLine().split(" ");
ArrayList<Integer> arr = new ArrayList<>();
for (int i = 0; i < n; i++) {
arr.add(Integer.parseInt(inp[i]));
}
int[][] dp = new int[n + 1][n + 1]; // 정답 = dp[0][n-1]
int[] sum = new int[n+1];
for (int i = 1; i < n+1; i++) {
sum[i] = sum[i-1]+ arr.get(i-1);
}
for (int len = 2; len <= n; len++) {
for(int start = 0;start < n;start++){
int end = start+len-1;
if(end >= n){
continue;
}
dp[start][end] = Integer.MAX_VALUE;
// stop 지점은 앞에 포함됨, stop < end
for(int stop = start; stop <end ; stop++){
dp[start][end] = Math.min(
dp[start][end],
dp[start][stop] + dp[stop+1][end] + sum[end+1] - sum[start]
);
}
}
}
System.out.println(dp[0][n-1]);
}
}
}