BOJ_11066_파일합치기
2차원 배열 DP(Dynamic Programming)을 이용해 파일을 합치는 최솟값을 구하는 문제
놓친 것
- 문제에 "소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고," 라는 대목이 있는데 문제를 세 번이나 읽었으면서 독해를 안 했다... 이것 때문에 접근 방법이 완전히 잘못됐었다. 문제를 더 꼼꼼하게 읽자!
- n개를 합친 것 + 1개까지는 구상을 잘 했는데 n개를 합친 것 + m개를 합친 것을 어떻게 구해야 할지 가늠이 안 됐다. 풀이를 보니 삼중 반복문과 sum 배열을 활용해서 여러 장을 합친 값들을 비교했다.
package BJO;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Stream;
public class BJO_11066_파일합치기 {
static int K;
static int[] costArr;
static int[][] dp;
static int[] sum;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
K = Integer.parseInt(br.readLine());
costArr = Stream.of(br.readLine().split(" ")).mapToIntparseInt).toArray(;
dp = new int[K + 1][K + 1];
sum = new int[K + 1];
for (int j = 1; j <= K; j++) {
sum[j] = sum[j - 1] + costArr[j - 1];
}
combineChapter();
}
}
static void combineChapter() {
for (int i = 1; i <= K; i++) {
for (int j = 1; i + j <= K; j++) {
int end = i + j;
dp[j][end] = Integer.MAX_VALUE;
for (int k = j; k < end; k++) {
dp[j][end] = Math.min(dp[j][end], dp[j][k] + dp[k + 1][end] + sum[end] - sum[j - 1]);
}
}
}
System.out.println(dp[1][K]);
}
}