[백준]1106번 파일합치기2️⃣

ynoolee·2021년 12월 13일
0

코테준비

목록 보기
73/146

11066번: 파일 합치기

[백준]11066번 파일합치기2️⃣

2022.02.08

이 문제는, 여러 장들이 “연속이 되도록 파일을 합쳐” 야 한다.

문제 풀이

  • 동적 계획법을 사용해야한다는 걸 떠올리는 건 어렵지 않다. 그림을 그려보면 된다 ( 이전에 풀이를 참고하자 )
    • dp[left][right] 는, left ~right 범위인 subset의 최소값을 세팅한다.

이전과 다른 풀이로 풀었는데(풀리긴 했음), 시간이 더 걸렸어서 

import java.io.*;
import java.util.*;

public class Main{

    public static int[] input; // 현재 테스트의 input
    public static int k; // 현재 테스트의 장의 개수
    public static int[][] dp = new int[500][500];
    public static int[][] sumCache = new int[500][500];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void settingNSolve() throws IOException {
        int t = Integer.parseInt(br.readLine());

        // 각 테스트는 두 개의 행으로 주어진다.
        for(int i = 0 ; i < t ; i ++){
            // init
            k = Integer.parseInt(br.readLine());
            input = new int[k];
            // init dp
            for(int j=0;j<k;j++){
                Arrays.fill(dp[j],-1);
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < k; j++) {
                input[j] = Integer.parseInt(st.nextToken());
                dp[j][j] = input[j];
                sumCache[j][j] = input[j];
            }
            // init sumCache
            sum();
            System.out.println(recur(0,k-1));
        }
    }
    public static int recur(int left, int right){

        if(dp[left][right]!=-1)return dp[left][right];

        //원소가 2개 인 경우
        if(right-left == 1){
//            System.out.println("[ "+left+","+right+" ] MIN : " +(input[left]+input[right]));
            return dp[left][right] = (input[left]+input[right]);
        }

        int tempSum = 0, min = Integer.MAX_VALUE;
        for(int i = left+1;i <= right;i++){
            tempSum = recur(left,i-1);
            tempSum += recur(i,right);
            // 범위 길이가 1보다 크면 sum 을 더해줘야할 듯!!!!!
            if( i-1-left > 0) tempSum += sumCache[left][i-1];
            if( right - i > 0) tempSum += sumCache[i][right];
            min = Math.min(min,tempSum);
        }
//        System.out.println("[ "+left+","+right+" ] MIN : " +(min));
        return dp[left][right] = min;
    }
    public static void sum(){
        for(int l = 0 ; l<k;l++){
            for(int r = l+1; r<k;r++){
                sumCache[l][r] = sumCache[l][r-1] + input[r];
            }
        }

    }

    public static void main(String[] args) throws IOException{
        settingNSolve();

    }
}

개선시키기

이전에 풀었던 방식을 다시 읽어보았다.

  • 구간을 나누어서 재귀적으로 수행하다보니, 반복되는 부분이 존재 → 동적 계획법을 수행해야한다.
  • 만약, 처음 생각하던 것 처럼, left ~ right 에 대한 구간을 subL과 subR 로 나누어, recur(left,i-1) + recur(i,right) 를 하고 나서, sum(left,right) 를 하기 위해서는, subset 중에서 , 개수가 1개밖에 없는 경우를 고려해 주어야 한다. (a1+a2) + a3 인 경우, 해답을 구할 때는, a1+a2 + a3 + (a1+a2) 를 해줘야한다. 이 때 a3 는 두 번 더해지는 애가 아니기 때문이다.
    • 이번에 풀 때의 나는, subset 중에서, 1개의 원소로만 이루어진 subset의 경우에는, sum의 대상에 포함시키지 않는 것으로 했었다.
      • 그러다보니, 매 번 subset의 사이즈를 check하고, 이에 따라 sum을 해줘야 했다.
    • 이전에 풀 때의 방법으로는 : dp의 모든 값을 -1 로 해 두되, dp[k][k] = 0 을 먼저 세팅해두는 것이 필요하다. 그렇다면 recur(left,left) 가 리턴하는 값은 0 일 것이고, sum(left,right)를 통해, a3 가 더해 질 수 있기 때문.
  • 또한, 2개의 원소로만 이루어진 left,right 범위인 경우에는,recur을 호출 했을 때 !

    1. dp에 -1이 아닌 값이 있는지 확인

    2. -1이면, 두 원소의 합을 dp에 세팅하고 리턴한다.

      를 수행하도록 하였다.

      그러다보니, 이 역시 recur을 호출할 때 매 번확인하는 if문이 하나 더 추가되는 것이 되어있었다.

      2개의 원소로만 이루어진 서브셋의 값의 경우에는, 초기에 미리 dp를 세팅해 놓을 수 있었다.

  • 처음 제출 했을 때 시간초과가 일어났었다.
    • 으로 하였었다. 하지만 틀렸어서 나는 sum(left,right) 를 계산하는 것이 부담인가 싶어, sumCache[left][right]를 bottom up 방식으로 먼저 채워넣고 이를 사용했다.
  • 이전 풀이와 이번 풀이를 합쳐서 다시 제출해보았다.
    • 이전 풀이에 + sum까지 캐싱하여 값을 사용하여 조금 더 빨라졌다.

항상 left <=right 이도록 하였기 때문에 sumCache의 초기화를 아래와같이 구현함

import java.io.*;
import java.util.*;

public class Main{

    public static int[] input; // 현재 테스트의 input
    public static int k; // 현재 테스트의 장의 개수
    public static int[][] dp = new int[500][500];
    public static int[][] sumCache = new int[500][500];
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;
    public static void settingNSolve() throws IOException {
        int t = Integer.parseInt(br.readLine());

        // 각 테스트는 두 개의 행으로 주어진다.
        for(int i = 0 ; i < t ; i ++){
            // init
            k = Integer.parseInt(br.readLine());
            input = new int[k];
            // init dp : 기본값 -1 , [i][i] 는 0 을 세팅 
            for(int j=0;j<k;j++){
                Arrays.fill(dp[j],-1);
            }
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j  <k; j++) {
                input[j] = Integer.parseInt(st.nextToken());
                dp[j][j] = 0;
                sumCache[j][j] = input[j];
            }
            // 원소가 2개인 경우 dp 에 미리 세팅하기 
            for(int l = 0; l < k-1;l++){
                dp[l][l+1] = input[l] + input[l+1];
            }
            // init sumCache
            initSumCache();
            // solve
            System.out.println(recur(0,k-1));
        }
    }
    public static int recur(int left, int right){
        if(dp[left][right]!=-1) return dp[left][right];
        int min = Integer.MAX_VALUE;
        for(int i = left+1;i <= right;i++){
            min = Math.min(min, recur(left,i-1)+recur(i,right));
        }
        min += sumCache[left][right];
        return dp[left][right] = min;
    }
    public static void initSumCache(){
        for(int l = 0 ; l<k;l++){
            for(int r = l+1; r<k;r++){
                sumCache[l][r] = sumCache[l][r-1] + input[r];
            }
        }
    }
    public static void main(String[] args) throws IOException{
        settingNSolve();
    }
}

[백준]11066번 파일합치기1️⃣

  • 두 개의 파일을 합쳐 → 임시파일을 생성
  • 파일을 합치는 것은 다음과 같이 이루어진다.
    • 파일 + 임시 파일
    • 파일 + 파일
    • 임시파일 + 임시파일
  • 이때 이렇게 합치는 것은 [ 연속적으로 합치는 것 ] 을 요구하고 있다.
  • 최종적으로 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하고 싶다.

예시 보고 이해하기

C1 C2 C3 C4
40 30 30 50 

C2 + C3 = X1 = 60
C1 + X1 = X2 =40 + 60 = 100
C4 + X2 = 50 + 100 = 150
또는 
C1+ C2 = Y1 = 70
Y1 + C3 = Y2 = 70 + 30 = 100
C4 + Y2 = 100 + 50 = 150

풀이 방법 ( 맞긴 했는데 가장오랜시간이 걸리는 방법일듯 )

풀이는 당연히 DP를 써야한다고 생각했다

  • 분할정복과 유사하게 분할을 해 나가는 방식을 생각했었다.
  • 자연스레 겹치는 구간들이 여러번 생길 것이기 때문에 DP를 생각했다

인접한 것 끼리만 더할 수 있다는 것

  • 테스트 하나당 500개의 장이 있을 수 있다.
  • 순서도 중요함
    • a1 a2 a3 a4 가 있을 때
    • a2+a3 → b1
    • b1 + a4 (+ b1 ) = b2
  • 분할정복 방식을 사용하면서, 백트랙킹을 하는 방법을 사용하면 안 되려나
  • 백트랙킹이라는게 결국은 한 번은 끝 까지 갔다가 오는 거임...
    • 우리에게 필요한 것은 어떤 것의 sum을 리턴하는 것 , 그리고 component1 과 component2
    • 그니까 백트랙킹은 아니라는 거임

챕터가 2개인 경우

→ 두개를 그냥 더하면 된다.

챕터가 3개 이상인 경우

a1 a2 a3

a1+ a2 = b1

b1 + a3

여기서 합은 → a1 + a2 + b1 + a3임

어떤 함수에서는

전체 구간을 → section1 , section 2 나눈다. → section1 + section2 를 리턴한다.

  • left, right가 존재할 때, 구간을 나누는 pivot이 있다고 해 보자
  • pivot은 left ≤ pivot < right 로 하고
    • 구간은 : [ left ~ pivot ] , [ pivot +1 ~ right ] 로 한다.
  • if : right

특정 구간을 분할하는 경우는 여러가지가 있어 보이지만, 결국은 하나의 pivot을 기준으로 left ~ pivot 그리고 pivot +1 ~ right로 나누어진다.

이것을 divide하여 원소가 1일 때 까지 나누다가, 합쳐가는 과정이다

어쨋거나 section의 값이 "최소가 나오게 하면 된다 "

  • divide한 section을 계산하는 값이 최소가 나오도록 구해서 , 분할해놓은 tree를 타고 올라가면됨.

import java.io.*;
import java.util.*;

public class Main{
    // dp 를 사용해야한다. divide 시켜놓고 합할 건데, 각 부분들은 최소 값을 갖도록 해야한다
    // 여기서 최소값은, a + b  = A , c + A = B 일 때, a + b + c + A 도 최소.. B도 최소여야하지 않나........
    // 근데 a + b + c + A가 최소면 B도 최소네
    // 아무튼 recur이 리턴해야하는 것은 무엇일까? 아니, 리턴을 해야하는걸까?
    // 현재 상황의, 현재까지 더한 값 : dp[left][i] + dp[i+1][right] + dp[left]
    public static int[][][] dp = new int[500][500][2]; // dp[left][right][0] : 여기까지 오는데 필요한값 dp[left][right][1] 은 리턴값
    // 현재 주어진 챕터
    public static int[] cur = new int[500] ;
    // 현재 주어진 챕터의 수
    public static int k;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static void setting() throws IOException{
        int t = Integer.parseInt(br.readLine());
        for(int i =0; i<t; i++){
            // 각 테스트
            k = Integer.parseInt(br.readLine());
            // input
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<k;j++){
                cur[j] = Integer.parseInt(st.nextToken());
            }
            // dp init
            init(k);
            recur(0,k-1);
            System.out.println(dp[0][k-1][0]);

        }

    }
    /*
    * 각 파일의 크기는 양의 정수로 주어지기 때문에 dp 값을 0으로 설정해도 될 듯
    * */
    public static void init(int k){

        for( int r=0; r<k;r++){
            for(int c=0;c<k;c++){
                dp[r][c][0] =0;
                dp[r][c][1] =0;
            }
            dp[r][r][1] = cur[r];
        }
    }

    // 현재까지오는데 더한 값 -> 현재 값은 포함하지 않음
    // 두 개의 원소로 이루어진 경우에는 -> [0]과 [1]이 같을 수 밖에
    // 좌측부분 까지 가는데 필요한 값을 dp[left][right][0] 을 통해 얻을 수 있다
    // 좌측에서 리턴되는 값은, 그냥 값...
    public static void recur(int left, int right){
        // return 값, 여기까지 오는데 필요한 값 을 구분하여 저장하도록 하자
        if(dp[left][right][1] != 0){
            return;
        }
        // 만약 right = left + 1 이라면 ?
        int minSum = Integer.MAX_VALUE;
        int min = Integer.MAX_VALUE;

        int curSum = 0,cur=0;
        for(int i =left;i<right;i++){
            recur(left,i);
            recur(i+1,right);
            curSum = 0;
            curSum += dp[left][i][0];
            curSum += dp[i+1][right][0];
            curSum += dp[left][i][1];
            curSum += dp[i+1][right][1];

            if(curSum < minSum ){
                minSum = curSum;
                min = dp[left][i][1] + dp[i+1][right][1];
            }
        }
        dp[left][right][0] = minSum;
        dp[left][right][1] = min;

    }

    public static void main(String[] args) throws IOException{

        setting();

    }
}

풀이 개선시키기

위의 풀이에서 굳이 dp를 3차원으로 할 필요가없었다.

  • 이제는 dp를 2차원으로 한다.
  • 이 dp[left][right]에는 left ~ right 까지의 파일을 [ 합치는 데 필요한 파일들의 합 ] 이다. 즉 위의 풀이의 dp[left][right][0] 값 만을 dp로 사용한다고 생각하면 된다.
    • 즉, left = right 일 때는 0 이다.
      • 위의 풀이에서 내가 dp[left][right][0] =0 을 했던 것과 같다.
    • divided section에 두개의 원소만이 있는 경우에 대해서는 미리 값을 따로 세팅해 두도록 한다.
      • dp[left][left+1] = cur[left] + cur[left+1]
  • 그리고 내가 혼란이 있었던 부분은 이건데 이는 💥💥문제에 대한 이해 자체가 부족했기 때문이다
    • recur(left,right) 에서 , i를 기준으로 section을 나눌 때,
    • 나눈 section에 대하여 이제 값을 구할 때
    • dp[left,i ] + dp[i+1,right ] 그리고 ( left~i ) 구간의 파일들을 모두 더한값, ( i~right) 구간의 파일을 모두 더한 값 을 더해야해! 이러고 있었는데
      • 이는 그냥 left ~ right까지 파일들을 모두 합하면 되는 거임
    • dp[left,i ] + dp[i+1,right ] + totalsum(left,right)
import java.io.*;
import java.util.*;

public class Main{
    // dp 를 사용해야한다. divide 시켜놓고 합할 건데, 각 부분들은 최소 값을 갖도록 해야한다
    // 여기서 최소값은, a + b  = A , c + A = B 일 때, a + b + c + A 도 최소.. B도 최소여야하지 않나........
    // 근데 a + b + c + A가 최소면 B도 최소네
    // 아무튼 recur이 리턴해야하는 것은 무엇일까? 아니, 리턴을 해야하는걸까?
    // 현재 상황의, 현재까지 더한 값 : dp[left][i] + dp[i+1][right] + dp[left]
    public static int[][] dp = new int[500][500]; // dp[left][right][0] : 여기까지 오는데 필요한값 dp[left][right][1] 은 리턴값
    // 현재 주어진 챕터
    public static int[] cur = new int[500] ;
    // 현재 주어진 챕터의 수
    public static int k;
    public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static StringTokenizer st;

    public static void setting() throws IOException{
        int t = Integer.parseInt(br.readLine());
        for(int i =0; i<t; i++){
            // 각 테스트
            k = Integer.parseInt(br.readLine());
            // input
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<k;j++){
                cur[j] = Integer.parseInt(st.nextToken());
            }
            // dp init
            init(k);
            System.out.println(recur(0,k-1));
        }
    }
    /*
    * 각 파일의 크기는 양의 정수로 주어지기 때문에 dp 값을 0으로 설정해도 될 듯
    * */
    public static void init(int k){
        for(int r=0;r<k;r++){
            for(int c=0;c<k;c++){
                dp[r][c] = -1;
            }
            dp[r][r] = 0;
        }
        for(int r=0;r<k-1;r++) dp[r][r+1] = cur[r]+cur[r+1];
    }

    // 현재까지오는데 더한 값 -> 현재 값은 포함하지 않음
    // 두 개의 원소로 이루어진 경우에는 -> [0]과 [1]이 같을 수 밖에
    // 좌측부분 까지 가는데 필요한 값을 dp[left][right][0] 을 통해 얻을 수 있다
    public static int recur(int left, int right){
        // return 값, 여기까지 오는데 필요한 값 을 구분하여 저장하도록 하자
        if( dp[left][right] != -1){
            return dp[left][right];
        }
        int sum = Integer.MAX_VALUE ;
        for(int i= left;i<right;i++){
            sum = Math.min(sum,recur(left,i)+recur(i+1,right));
        }
        // left ~ right 파일 합
        for(int i = left; i <= right ; i++){
            sum += cur[i];
        }
        dp[left][right] = sum;
        return sum;
    }

    public static void main(String[] args) throws IOException{
        setting();
    }
}
profile
ynoolee
이전 포스트

# [프로그래머스] 멀쩡한 사각형

다음 포스트

[백준]17143번 낚시왕

0개의 댓글