Baekjoon Online Judge

algorithm practice

- 단계별 문제풀기

23. 동적 계획법2

조금 더 어려운 동적 계획법 문제를 풀어 봅시다.

Java / Python

1. 파일 합치기

11066번

파일을 합쳐 하나로 모으는 최소 비용을 구하는 문제

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

• Java

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = null;        
		int T = Integer.parseInt(br.readLine());
        
		for (int n = 0; n < T; n++) {
			int k;
			int[] novel;
			int[] sum;
			int[][] dp;
            
			k = Integer.parseInt(br.readLine());
			novel = new int[k + 1];
			sum = new int[k + 1];
			dp = new int[502][502];

			st = new StringTokenizer(br.readLine());
			for(int i = 1; i <= k; i++) {
				novel[i] = Integer.parseInt(st.nextToken());
				sum[i] = sum[i - 1] + novel[i];
			}

			for(int i = 2; i <= k; i++){
				for(int j = i - 1; j > 0; j--){
					dp[j][i] = 999999999;
					for(int s = j; s <= i; s++)
						dp[j][i] = Math.min(dp[j][i], dp[j][s] + dp[s + 1][i]);
      
					dp[j][i] += sum[i] - sum[j - 1];
				}
			}           
			bw.write(dp[1][k] + "\n");
		}
		bw.flush();
		bw.close();
		br.close();
	}
}

• Python

import sys
 
n = int(sys.stdin.readline())
 
while n > 0:
    n -= 1
    K=int(sys.stdin.readline())
    file_list=list(map(int,sys.stdin.readline().split()))
    dp=[[0 for _ in range(K)] for _ in range(K)]
    sum=[0]*(K+1)    # 1~K 파일크기합 한번 합칠때 추가비용
    sum[1]=file_list[0]
    for i in range(1,K+1):    # i번째 파일까지의 합
        sum[i]=sum[i-1]+file_list[i-1]
        
    # Knuth's Optimization 각 구간에서 나오는 k 저장
    knuth = [[0 for _ in range(K)] for _ in range(K)]  
    for i in range(K):    #초기화
        knuth[i][i]=i
 
    for x in range(1,K):    # x만큼 더한 구간 구하기
        for i in range(K-x):    # 시작위치 i에서 i+x까지 구간
            j=i+x
            dp[i][j]=999999999999
            for k in range(knuth[i][j-1],knuth[i+1][j]+1): # 범위에 knuh 최적화를 적용
                if k < K - 1 and dp[i][j] > dp[i][k] + dp[k+1][j]+sum[j+1]-sum[i]: # 최솟값 찾기
                    dp[i][j]=dp[i][k]+dp[k+1][j]+sum[j+1]-sum[i]
                    knuth[i][j]=k
            
    print(dp[0][K-1])