11066번 - 파일 합치기
문제 풀이 시간 : 2시간
문제 요약:
- 여러 개의 파일을 합쳐 하나의 파일을 만들려고 한다.
- 파일을 합치는 최소 비용을 구하라.
문제 풀이
이 문제를 보자마자 우리가 알고리즘 시간에 배웠던 허프만 트리가 생각났다.
그래서 바로 우선순위 큐로 코드를 쉽게 짤 수 있었다.
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static PriorityQueue<Integer> pq;
public static int calc() {
int temp = 0;
while (pq.size() > 1) {
int a = pq.poll();
int b = pq.poll();
temp += a + b;
pq.add(a + b);
}
return temp;
}
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++) {
pq = new PriorityQueue<>();
int K = Integer.parseInt(br.readLine());
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < K; j++) {
pq.add(Integer.parseInt(st.nextToken()));
}
System.out.println(calc());
}
}
}그런데 예제 부터가 틀리게 나온다…
2번 예제에서 답은 864라고 나오지만
내가 작성한 코드에서는 826이 나온다.
그래서 내가 코드를 잘못 짰나? 하고 직접 허프만 트리를 그려보았다.
근데 그래도 826이 나온다..
이건 내가 더 낮은 수가 나오는데 답이 틀릴수가 없다 생각하고
문제의 오류를 찾았구나???
했는데??
알고보니
임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고
라는 문장이 문제 속에 숨어있었다.
즉, 파일의 순서대로 합쳐야 되는 것이다.
내가 짠 우선순위 큐를 활용한 풀이는 순서를 섞어버리기 때문에 해당 문제의 조건을 만족하지 못한 것이다.
그래서 다시 풀이를 생각하다가 이건 DP다!! 라는 생각을 했다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
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++) {
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N + 1][N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
arr[j][j] = Integer.parseInt(st.nextToken());
}
for (int j = 0; j < N - 1; j++) {
for (int k = 1; k <= N - 1 - j; k++) {
int temp = Math.min(arr[k][k + j] + arr[k + 1 + j][k + 1 + j], arr[k][k] + arr[k + 1][k + 1 + j]);
arr[k][k + 1 + j] = temp;
}
}
for (int j = 1; j <= N; j++) {
for (int k = 1; k <= N; k++) {
System.out.printf(arr[j][k]+" ");
}
System.out.println();
}
}
}
}이렇게 어찌저찌 DP 코드를 짜서 파일을 합치긴 하는데…
최소 비용을 구하는 방법을 도저히 모르겠어서
결국 형님들의 코드를 참고하게 되었다.
여기서 arr은 dp를 계산한 배열이고,
arr[i][i]는 i번째 페이지 부터 i번째 페이지 까지의 합이다.
즉, arr[i][i] = num[i]
arr[i][i+1] = num[i] + num[i+1]이 된다.
그럼 arr[i][i+2]는?
arr[i][i] + arr[i+1][i+2] + (num[i] + num[i+1] + num[i+2])
arr[i][i+1] + arr[i+2][i+2] + (num[i] + num[i+1] + num[i+2])
중 작은 값이 될 것이다.
그래서 결국 arr[i][j]를 구하려면?
i ≤ temp < j 인 temp를 가지고
arr[i][temp]+arr[temp+1][j]+num[i] + num[i+1] + … +num[j]
를 다 해보면 되는 것이다.
결국 아래와 같은 코드가 나오게 된다.
for (int j = 1; j <= N; j++) {
for (int from = 1; from + j <= N; from++) {
int to = from + j;
arr[from][to] = Integer.MAX_VALUE;
for (int t = from; t < to; t++) {
arr[from][to] = Math.min(arr[from][to], arr[from][t] + arr[t+1][to] + sum[to] - sum[from - 1]);
}
}
}최종 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
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++) {
int N = Integer.parseInt(br.readLine());
int[][] arr = new int[N + 1][N + 1];
int[] num = new int[N + 1];
int[] sum = new int[N + 1];
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 1; j <= N; j++) {
num[j] = Integer.parseInt(st.nextToken());
sum[j] = sum[j - 1] + num[j];
}
for (int j = 1; j <= N; j++) {
for (int from = 1; from + j <= N; from++) {
int to = from + j;
arr[from][to] = Integer.MAX_VALUE;
for (int t = from; t < to; t++) {
arr[from][to] = Math.min(arr[from][to], arr[from][t] + arr[t+1][to] + sum[to] - sum[from - 1]);
}
}
}
System.out.println(arr[1][N]);
}
}
}함께 읽으면 좋은 글
5430번 - AC
함수 R은 배열을 뒤집는 연산 함수 D는 첫 번째 원소를 버리는 연산 단, 배열이 비어 있을 때 D를 수행하면 error 주어진 함수 문자열을 순서대로 수행한 뒤 최종 배열을 출력하는 문제 처음에는 문제 설명 그대로 R이 나올 때마다 배열을 실제로 뒤집고, D가 나오면 맨 앞…
1966번 - 프린터 큐
여러 문서가 큐에 들어 있고, 각 문서마다 중요도가 있음 맨 앞 문서를 확인했을 때, 더 높은 중요도의 문서가 뒤에 하나라도 있으면 맨 뒤로 보냄 그렇지 않으면 바로 인쇄 특정 위치의 문서가 몇 번째로 인쇄되는지 구하는 문제 이 문제는 프린터의 동작을 그대로 구현하면 되는…
1158 - 요세푸스 문제
1번부터 N번까지 사람이 원형으로 앉아 있음 순서대로 K번째 사람을 제거 모든 사람이 제거될 때까지 반복 제거되는 순서를 출력하는 문제 이 문제는 원형으로 순회하면서 K번째를 제거하는 과정을 그대로 구현하면 된다.
2164번 - 카드2
1부터 N까지 카드가 순서대로 쌓여 있음 맨 위 카드를 버리고, 그다음 맨 위 카드를 맨 아래로 옮기는 과정을 반복 마지막에 남는 카드 번호를 구하는 문제 이 문제는 규칙을 찾기보다, 문제에서 하라는 과정을 그대로 구현하면 된다. 카드 더미에서 반복되는 동작은 두 가지다.