[BOJ-11066] 파일합치기

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

11066번: 파일 합치기

---

[풀이]

참고 블로그1: https://blog.naver.com/tjdwns0920/221135677693

참고 블로그2: https://js1jj2sk3.tistory.com/search/11066

참고 블로그3: https://kyunstudio.tistory.com/75

---

[python] 시간초과 ㅠㅠ;

# -*- coding: utf-8 -*-
import sys

def main():
    T=int(sys.stdin.readline())
    for _ in range(T):
        # K: 소설을 구성하는 장의 수 (3<=K<=500)
        K= int(sys.stdin.readline())
        cost=list(map(int, sys.stdin.readline().split()))
        dp=[[0]*(K+1) for _ in range(K+1)] #초기화
        s=[0]*(K+1) #초기화

        for i in range(1,K+1):
            #cost는 시작인덱스가 0부터이다..
            #1부터 i까지의 합
            s[i]=s[i-1]+cost[i-1]
        for d in range(1, K):
            for tx in range(1,K+1-d):#ty=tx+d<=K
                ty=tx+d #ty:도착점
                dp[tx][ty]=10001 #tx->ty까지 최소비용 10001로 초기화

                for mid in range(tx, ty):
                    #tx->ty 까지 도달하는데 최소비용을 구한다.
                    #dp[tx][ty], dp[tx][mid]+dp[mid+1][ty] +s[ty]+s[tx-1]
                    # dp[tx][mid]: tx->mid까지의 최소비용
                    # dp[mid+1][ty]: mid+1-> ty까지의 최소비용
                    dp[tx][ty]=min(dp[tx][ty], dp[tx][mid]+dp[mid+1][ty]+s[ty]-s[tx-1])
                    
        print(dp[1][K])#1부터 K까지 최소비용
        

if __name__=='__main__':
    main()

---

[java]

import java.util.Scanner;
public class Main{
	//최대 500개..
	static int dp[][];
	static int sum[];
	static int cost[];
	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int T= sc.nextInt();
		int K;
		for(int t=0; t<T; t++) 
		{
			//K입력(K: 소설을 구성하는 장의 수)
			K=sc.nextInt();
			
			//초기화
			dp= new int[501][501];
			sum= new int[501];
			cost= new int[501];
			for(int i=0; i<K; i++)
				cost[i]=sc.nextInt();
			
			//0부터 0까지의 합
			sum[0]=cost[0];
			
			//0부터 i까지의 합
			for(int i=1; i<K; i++)
				sum[i]+=sum[i-1]+cost[i];
			
			//초기값저장
			for(int i=0; i<K-1; i++)
				dp[i][i+1]=cost[i]+cost[i+1];
			
			for(int gap=2; gap<K; gap++)//i와 j간 gap이 3이상일때 
			{
				for(int i=0; i+gap<K; i++) 
				{
					int j=i+gap;
					dp[i][j]=Integer.MAX_VALUE; //무한대
					
					for(int mid=i; mid<j; mid++)//i~j 사이의 k값
						dp[i][j]=Math.min(dp[i][j], dp[i][mid]+dp[mid+1][j]+sum(sum,i,j));
				}
			}
			System.out.println(dp[0][K-1]);
		}
	}
	
	public static int sum(int sum[], int i, int j) 
	{
		if(i==0)
			return sum[j];
		else
			return sum[j]-sum[i-1];
	}
}