[JAVA] 백준 11066 파일 합치기

https://www.acmicpc.net/problem/11066

11066번: 파일 합치기

 

- 소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 

 

- 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 

 

- 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 떄, 최종적인 한개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.

 

- 예를들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40,30,30,50 이라고 하자.

- 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용이 60이 필요하다. 

- 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 

- 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 

- 따라서 , 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150 = 310이다.

 

- 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300이다.

 

- 소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소 비용을 계산하는 프로그램을 작성 

 

 

문제 풀이 

 

 

동적 프로그래밍(DP, 동적 계획법)

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드) (tistory.com)

[Algorithm] 동적 프로그래밍 (DP, 동적 계획법) 이해하기 (+ 예제 코드)

 

- "큰 문제"를 "부분 문제"로 나누고 "부분 문제"의 정답으로 "큰 문제"의 해답을 찾아가는 알고리즘 설계 기법

- 분할 정복과의 차이점은 "부분 문제"의 특성

 

1)중복되는 부분 문제 (Overlapping Subproblem)

 

- 동적 프로그래밍은 작게 쪼개진 "부분 문제"가 중복돼서 나타남

- 분할 정복은 "큰 문제"가 "유니크한 부분 문제"로 나뉨

 

2) 최적 부분 구조(Optinal Substructure)

 

-"큰 문제"의 해를 찾기 위한 연산과 "부분 문제"의 해를 찾기 위한 연산이 동일해야 하며 "부분 문제"의 해를 조합해  "큰 문제"의 해를 찾을 수 있는 구조 

 

3) 메모이제이션(memoization)

 

- 컴퓨터 프로그램이 동일한 계산을 반복적으로 해야 할 때, 이전에 계산한 값을 메모리에 저장하여 중복적인 계산을 제거하여 전체적인 실행 속도를 빠르게 해주는 기법으로 동적 계획법의 핵심이 되는 기술

 

4) 접근 방법 

 

Top - Down 

 - 큰 문제를 작은 문제로 나눈다. 

 - 작은 문제를 푼다. 

 - 재귀 호출을 하는 방식 

 

Bottom - up

- 문제를 크기가 작은 문제부터 차례대로 쓴다. 

- 문제의 크기를 조금씩 크게 만들면서 문제를 푼다. 

- 작은 문제를 풀면서 큰 문제의 답을 구한다. 

 

[자바] 백준 11066 - 파일 합치기 (java) - Nahwasa

[자바] 백준 11066 - 파일 합치기 (java)

백준 11066번 : 파일 합치기 [Java] 소스 코드를 기록하는 남자 (tistory.com)

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

- 만약 2개의 파일 C1, C2를 합치는 경우 최소 비용은 C1+C2가 된다.

- 파일이 3개라면 (C1+C2)+C3 또는 C1+(C2+C3)의 비용 중 낮은 비용을 고르면 된다.

- 파일이 4개라면 아래의 경우 중 최소 비용을 고르면 된다.

  1) C1+(C2+(C3+C4)

  2) (C1+C2)+(C3+C4)

  3) ((C1+C2)+C3)+C4

 

- 즉, 파일이 N개일 경우 최소 비용은  아래의 경우 중 최소 비용을 고르면 된다.

  1) C1 + (C2~Cn의 합)

  2) (C1~C2의 합) + (C3 ~ Cn의 합)

  3) (C1~C3의 합) + (C4~Cn의 합)

  ...

   n) (C1~Cn-1의 합) + Cn

 

- 종합하면 재귀적으로 점점 더 작은 조합의 최소 비용을 알아야 하고, 그렇다면 메모리에 특정 구간의 최소비용을 저장해두면 된다. 

 

- memo[i][j] 에 i~j까지 파일을 합치는데 드는 최소 비용을 저장

- 점화식 memo[from][to] = min(memo[from][to], memo[from][divide] + memo[divide+1][to] + sum[to] - sum[from-1]을 이용해 갱신

 

 

정답

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main
{

    static int arr[];
    static int memo[][];
    static int sum[]; //i부터 j까지의 파일을 더한 총합
    
    public static void main(String[] args) throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        int T = Integer.parseInt(br.readLine());
        StringTokenizer st;
        
        while(T-->0)
        {
        	int K = Integer.parseInt(br.readLine());
        	
        	arr = new int[K+1];
        	memo = new int[K+1][K+1];
        	sum = new int[K+1];
        	
        	st = new StringTokenizer(br.readLine());
        	for(int i=1; i<=K; i++)
        	{
        		arr[i] = Integer.parseInt(st.nextToken());
        		sum[i] = sum[i-1] + arr[i];
        	}
        	
        	//n: 구해야 하는 범위의 크기 
        	for(int n=1; n<=K; n++)
        	{
        		//from : 합치는 범위의 시작부분
        		for(int from=1;from+n<=K; from++)
        		{
        			int to = from+n;
        			memo[from][to] = Integer.MAX_VALUE;
        			
        			//divide : 구해야 하는 범위를 두 부분으로 나누는 기준점
        			for(int divide = from; divide<to; divide++)
        			{
        				memo[from][to] = Math.min(memo[from][to], memo[from][divide]+memo[divide+1][to] + sum[to] - sum[from-1]);
        			}
        		  
        		}
        	}
        	
        	bw.write(String.valueOf(memo[1][K]));
        	bw.newLine();
        }
        bw.flush();
        bw.close();
        
    }
}