[백준][Java] 11066번 파일 합치기

며칠 동안 고민했는데도 스스로 해결 못했습니다.

풀이과정을 보아도 대충 무슨 말하는지는 알아는 먹겠는데

책의 부분을 합치는 과정에 필요한 3중 for문이 왜 저런 식으로

구성되어야 하는지 모르겠고

마지막에 sum을 추가해주는 이유는 알겠는데

어째서 저런 식으로 몇줄 끄적인게

모든 책 페이지의 최소 합들을 구분하여

dp배열에 저장되는지도 머릿속에 그려지지가 않습니다.

시간을 많이 썼는데도 짐작조차 못했습니다..

참고 코드 : http://js1jj2sk3.tistory.com/3

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 36 37 38 39 40 41 42

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int T = sc.nextInt(); int[][] dp; for(int t=0; t<T; t++) { int K = sc.nextInt(); int[] sum=new int[K+1]; dp=new int[K+1][K+1]; int input; for(int j=1; j<=K; j++) { input=sc.nextInt(); sum[j]+=sum[j-1]+input; } for (int k = 1; k < K; k++) { for (int i = 1; i <= K - k; i++) { dp[i][i + k] = Integer.MAX_VALUE; for (int j = i; j < i + k ; j++) { dp[i][i + k] = Math.min(dp[i][i + k], dp[i][j] + dp[j+1][i + k]); } dp[i][i + k] += sum[i + k] - sum[i - 1]; } } System.out.println(dp[1][K]); } } }