[백준] 11066번 파일 합치기
문제 설명
https://www.acmicpc.net/problem/11066
문제 풀이
- 처음엔 순서를 마음대로 정할 수 있는 줄 알고 그리디 알고리즘으로 접근했으나 각 파일의 순서는 변경할 수 없어 다이나믹 프로그래밍으로 풀이하였다.
- 문제 풀이에 사용된 점화식은 아래와 같다.
- DP[from][to] : from 인덱스에서 to 인덱스까지 파일 합치기 최소 비용 리턴
- sum[from][to] : from 인덱스에서 to 인덱스까지 파일 크기 총합
- DP[from][to] = MIN(DP[from][i] + DP[i+1][to] + sum[from][to]) (from <= i < to)
소스 코드 (JAVA)
import java.io.*;
public class Main {
public static int T, K;
public static int INF = 987654321;
public static int[] arr = new int[500];
public static int[][] dp = new int[500][500];
public static int[][] sumArr = new int[500][500];
public static void init() {
for (int i = 0; i < K; i++) {
int tmpSum = 0;
for (int j = 0; j < K; j++) {
if (j >= i) tmpSum += arr[j];
dp[i][j] = INF;
sumArr[i][j] = tmpSum;
}
}
}
//from부터 to까지의 파일합치기 합의 최솟값 출력
public static int solve(int from, int to) {
//기저 조건
if (from == to) return 0;
if (dp[from][to] != INF) return dp[from][to];
int result = INF;
for (int i = from; i < to; i++) {
result = Math.min(result, sumArr[from][to] + solve(from, i) + solve(i+1, to));
}
return dp[from][to] = result;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
T = Integer.parseInt(br.readLine());
for (int t = 0; t < T; t++) {
K = Integer.parseInt(br.readLine());
String[] input = br.readLine().split(" ");
for (int i = 0; i < K; i++) {
arr[i] = Integer.parseInt(input[i]);
}
init();
bw.write(solve(0, K-1) + "\n");
}
br.close();
bw.flush();
bw.close();
}
}
Author And Source
이 문제에 관하여([백준] 11066번 파일 합치기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ddongh1122/백준-11066번-파일-합치기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)