<Algorithm> 209. 파일합치기(BOJ)

1. 11066번 파일합치기(BOJ)

   사용 알고리즘 : 구간합, DP  

• 1차원을 2차원 DP로 생각해야하는 문제 , 정답률이 50퍼센트여서 쉬울 줄 알았는데 되게 어렵게 느껴졌다, 

• 다른 블로그를 보면서도 이해가 잘 되지 않았는데 3중 for문 구간합이 섞여있어서 더 그랬던 것 같다.

문제에 대한 접근&생각

1. 파일의 개수는 500개, 2개씩 처리 ( 순서상관없이) -> 경우의 수가 너무 많음 -> DP!
2. DP[j][i] = min(DP[j][i], DP[j][k] + DP[k+1][i])-> j와 i 구간의 최솟값!
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

import java.util.Scanner;   public class Main {     public static void main(String[] args) {         Scanner sc = new Scanner(System.in);         int test = sc.nextInt();         /***************************          * partSum과 DP를 이용하여           * 구간의 최솟값을 구한다.          ***************************/         for(int t = 0; t < test; t++) {             int n = sc.nextInt();             int[] CDpartSum = new int[n];             int[][] dp = new int[n][n];             int accu = 0;             for(int i = 0; i < n; i++) {                 accu += sc.nextInt();                 CDpartSum[i] = accu;             }             for(int i = 1; i < n ; i++) {                 for(int j = i-1; j >= 0; j--) {                     dp[j][i] = Integer.MAX_VALUE;                     for(int k = j; k < i; k++) {                         dp[j][i] = Math.min(dp[j][i],dp[j][k]+dp[k+1][i]);                      }                     if(j-1>=0)                         dp[j][i] += (CDpartSum[i] - CDpartSum[j-1]);                     else                         dp[j][i] += CDpartSum[i];                 }             }             System.out.println(dp[0][n-1]);         }     } }   Colored by Color Scripter

cs

참고 & 출처  

https://www.crocus.co.kr/1073