이 문제를 푸는데에있어 가장 결정적인 코드는 다음과 같습니다.

// start 인덱스부터 end 인덱스까지의 합성에 필요한 총량
static int cost(int start, int end) {
		
    ....
    
    int ret = Integer.MAX_VALUE;//더미값

	for (int i = start; i < end; i++) {
		ret = Math.min(ret, cost(start, i) + cost(i + 1, end));
	}		
   	ret += start~end까지의 파일의 합
    ....
    
	return ret;
}

함수의 다음과 같습니다.

start 지점부터 end 지점까지 파일들을 합치는데에 필요한 비용

그리고 함수의 내부구현을 보면 다시 자기 자신을 i라는 기준으로 나누어서 재귀 호출합니다.

예시로 다음 그림처럼 메소드가 뻗어나갈 것입니다.

i=1일 때를 보겠습니다.

cost(0,0)은 파일을 합치는 비용이 없으므로 0입니다.

cost(1,2)라면 40 + 50 = 90의 합치는 비용이 필요하게 됩니다.

i=2일 때를 보겠습니다.

cost(0,1)은 파일을 합치는 비용이 30+40 = 70이 됩니다.

cost(2,2)은 파일을 합치는 비용이 없습니다.

문제가 파일을 합칠 때 비용이 최소로 나오게 하라했으므로 다음과 같은 코드가 나오게 된것입니다.

int ret = Integer.MAX_VALUE;//더미값
for (int i = start; i < end; i++) {
	ret = Math.min(ret, cost(start, i) + cost(i + 1, end));
}

위의 코드까지는 중간 과정들에 대한 비용이고 마지막으로 start~end까지의 파일들의 합을 더해줘야합니다. 무슨 말이냐면

다음과 같이 위의 코드가 나타내는 것은 노란 박스 부분이고, 마지막에 남은 합성 비용을 더해야 하는데 이는 start~end까지의 파일 합(30+40+50=120)과 같습니다.

재귀 함수를 만들었으니 이 함수에 캐쉬배열을 만들어 반복적으로 계산하는 일이 없도록 합니다.

전체 소스는 다음과 같습니다.

import java.util.Arrays;
import java.util.Scanner;

public class Exam11066 {

	static int[] arr;
	static int[][] cache;//합성 비용
	static int[][] s;
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int t, k;
		t = sc.nextInt();

		while (t-- > 0) {
			k = sc.nextInt();
			arr = new int[k];
			cache = new int[k][k];
			s = new int[k][k];
			
			// 입력
			for (int i = 0; i < k; i++) {
				arr[i] = sc.nextInt();
				Arrays.fill(cache[i], -1);
				Arrays.fill(s[i], -1);
				cache[i][i] = 0; // 파일을 합치는 비용 없음
			}
			
			System.out.println(cost(0,k-1));

		}
		sc.close();
	}

	// start ~ end까지 합성하는데에 필요한 총량
	static int cost(int start, int end) {
		//이미 계산된 것
		if (cache[start][end] != -1)
			return cache[start][end];

		int ret = Integer.MAX_VALUE;

		for (int i = start; i < end; i++) {
            //최소값((시작~i) + (i~끝))
			ret = Math.min(ret, cost(start, i) + cost(i + 1, end));
		}
		ret += sum(start,end);
		cache[start][end] = ret;

		return ret;
	}
	//start파일에서부터 end파일까지의 총합
	static int sum(int start, int end) {
		if(s[start][end]!=-1)
			return s[start][end];
		
		int sum = 0;
		
		for (int i = start; i <= end; i++) {
			sum += arr[i];
		}
		
		s[start][end] = sum;
		
		return sum;

	}
}