[11066] 파일 합치기
🤔 문제 설명
소설가인 김대전은 소설을 여러 장(chapter)으로 나누어 쓰는데, 각 장은 각각 다른 파일에 저장하곤 한다. 소설의 모든 장을 쓰고 나서는 각 장이 쓰여진 파일을 합쳐서 최종적으로 소설의 완성본이 들어있는 한 개의 파일을 만든다. 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다. 두 개의 파일을 합칠 때 필요한 비용(시간 등)이 두 파일 크기의 합이라고 가정할 때, 최종적인 한 개의 파일을 완성하는데 필요한 비용의 총 합을 계산하시오.
예를 들어, C1, C2, C3, C4가 연속적인 네 개의 장을 수록하고 있는 파일이고, 파일 크기가 각각 40, 30, 30, 50 이라고 하자. 이 파일들을 합치는 과정에서, 먼저 C2와 C3를 합쳐서 임시파일 X1을 만든다. 이때 비용 60이 필요하다. 그 다음으로 C1과 X1을 합쳐 임시파일 X2를 만들면 비용 100이 필요하다. 최종적으로 X2와 C4를 합쳐 최종파일을 만들면 비용 150이 필요하다. 따라서, 최종의 한 파일을 만드는데 필요한 비용의 합은 60+100+150=310 이다. 다른 방법으로 파일을 합치면 비용을 줄일 수 있다. 먼저 C1과 C2를 합쳐 임시파일 Y1을 만들고, C3와 C4를 합쳐 임시파일 Y2를 만들고, 최종적으로 Y1과 Y2를 합쳐 최종파일을 만들 수 있다. 이때 필요한 총 비용은 70+80+150=300 이다.
소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.
🤨 제한 사항
- 첫 입력 때 T개의 테스트 데이터를 받습니다.
- 각 테스트 데이터의 첫 행에는 소설을 구성하는 장의 수를 나타내는 양의 정수 K(3 <= K <= 500)가 주어집니다.
- 각 테스트 데이터의 두 번째 행에는 1장부터 K장까지 수록한 파일의 크기를 나타내는 양의 정수 K개가 주어집니다.
- 파일의 크기는 10000을 초과하지 않습니다.
😀 입출력 예
| 입력 | 출력 |
| 2 4 40 30 30 50 15 1 21 3 4 5 35 5 4 3 5 98 21 14 17 32 |
300 864 |
👩🏫 어떻게 풀어요?
- 이 과정에서 두 개의 파일을 합쳐서 하나의 임시파일을 만들고, 이 임시파일이나 원래의 파일을 계속 두 개씩 합쳐서 소설의 여러 장들이 연속이 되도록 파일을 합쳐나가고, 최종적으로는 하나의 파일로 합친다.
- 소설의 각 장들이 수록되어 있는 파일의 크기가 주어졌을 때, 이 파일들을 하나의 파일로 합칠 때 필요한 최소비용을 계산하는 프로그램을 작성하시오.
문제를 풀기 전에 문제를 자세히 읽어봐야지 제대로 풀 수 있는 문제입니다. 문제를 제대로 안 읽고 풀었다가는 여러 장들이 연속이 되도록 파일을 합쳐나간다는 규칙을 지키지 않은 알고리즘을 만들게 됩니다. 이 문제는 인접하지 않은 장은 합칠 수 없고, 서로 인접한 상태여야지만 합칠 수 있습니다. 이러한 방식으로 합쳐나가며 모든 장을 합치는데 필요한 최소 비용을 구하는 것이지요.
먼저 40 30 30 50 이라는 파일 크기가 있다고 가정을 하고 문제를 풀어보도록 하겠습니다.
맨 앞의 40과 30을 더했을 때는 총 70이라는 비용을 사용하여 하나의 파일로 합칠 수 있습니다. 이렇게만 보면 간단해 보이지만, 여기서 하나의 파일이 늘어난다면 이야기가 달라지게 됩니다.
40, 30, 30, 50 이라는 파일이 있을 때, 첫 번째 파일부터 세 번째 파일까지의 최소 비용의 합을 구하기 위해서는 2가지 경우를 비교해 볼 수 있습니다. 먼저 40과 30을 합치고 마지막 30을 합치는 방법과, 30과 30을 합치고 마지막에 40을 합치는 방법의 경우가 있습니다.
두가지 경우의 방법 모두 잘 보시면, 앞에서 했던 연산을 반복하고 있습니다. 첫 번째 방법의 경우, 40과 30을 합치는 작업이 다시 반복되고 있고, 두 번째 방법의 경우에는 30과 30을 합치는 방법이 반복되고 있습니다. 즉, 일반적인 방법으로 풀면 같은 연산을 반복하기 때문에 시간 초과가 발생하게 될 것이며, 해당 문제는 동적 할당법을 이용해 풀어야 한다는 것을 알 수 있습니다. 또한 모든 파일을 합쳤을 때의 최소 비용을 구하기 위해서는 각 방법마다 나오는 비용이 최소가 되어야 한다는 것도 알 수 있습니다. 40, 30, 30, 50을 모두 합쳤을 때 나오는 최소비용을 구하기 위해서는 반드시 위 그림에서는 두 번째 방법을 택해야 하는 것이죠. 그렇지 않으면 최소 비용으로 만들 수 없습니다.
40, 30, 30, 50 이라는 파일이 있을 때,
40 + 30
30 + 30
30 + 50
40 + 30 | 30 = (40 + 30) + (40 + 30 + 30)
40 | 30 + 30 = (40 + 30+ 30) + 30
30 + 30 | 50 = (30 + 30) + (30 + 30 + 50)
30 | 30 + 50 = (30 + 30 + 50) + (30 + 50)
...
첫 번째 부터 4번째 파일인 50까지의 최소 비용을 구하기 위해서는 각각 인접한 장끼리 합한 값을 계속해서 연산해 주고 있는 것을 알 수 있습니다. 따라서 동적 할당법을 위한 배열 말고도, 인접한 장끼리 미리 더한 값을 저장해 둔 sum 배열을 사용할 것 입니다.
위의 경우라면 sum 배열에는 다음과 같은 값이 저장됩니다.
sum[0] = 0
sum[1] = 40
sum[2] = 40 + 30 (첫번째 장과 두 번째 장의 합) = 70
sum[3] = 70 + 30 (첫번째 장 ~세 번째 장의 합) = 100
sum[4] = 100 + 50 (첫번째 장 ~네 번째 장의 합) = 150
그리고 각 구간의 최소 비용을 저장하기 위해 i 번째 장 ~ j 번째 장까지 합치는 최소 비용을 저장하는 2차원 배열인 dp를 사용하겠습니다.
dp[i][j] = i 번째 장 ~ j 번째 장까지 합치는 최소 비용
dp[i][i + 1] = sum[i + 1] - sum[i - 1]
ex)
dp[1][2] = 첫 번째 장 ~ 두 번째 장까지 합치는 최소 비용 = sum[2] - sum [0] = 70
dp[2][3] = 두 번째 장 ~ 세 번째 장까지 합치는 최소 비용 = sum[3] - sum [1] = 60
dp[3][4] = 세 번째 장 ~ 네 번째 장까지 합치는 최소 비용 = sum[4] - sum [2] = 80
만약 40, 30, 30의 파일을 합친다고 가정을 해볼 때 구할 수 있는 경우는 위의 그림에서 보았던 것 처럼 2가지 입니다. 2가지 중에서 최소값을 저장해야 하기 때문에 Math.min을 사용해서 저장합니다. 또한 40 + 30 을 먼저 연산하고 30과 합칠 것인지, 30 + 30을 먼저 연산하고 40과 합칠 것인지 기준을 정하는 변수 값이 필요합니다. 여기서는 k라고 정의하겠습니다.
40, 30, 30을 합쳐 보는 경우에서 2가지 방법으로 구할 수 있다면, k 변수를 사용해서 다음과 같은 식을 만들 수 있습니다.
dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k + 1][j] + sum[i + 1] - sum[i - 1])
30 + 30의 최소 비용을 구하고 40을 합치는 경우의 식
dp[1][3] = Math.min(dp[1][3], dp[1][1] + dp [2][3] + sum[3] - sum[0])
40 + 30의 최소 비용을 구하고 30을 합치는 경우의 식
dp[1][3] = Math.min(dp[1][3], dp[1][2] + dp [3][3] + sum[3] - sum[0])
코드에서는 위의 식을 수행하기 전에 해당 위치에 Infinity 값을 넣어 줌으로서 먼저 입력된 값이 항상 최소값으로 설정되게 하였고, dp [1][1] 이나 dp [2][2]의 경우에는 합치는 것이 아니기 때문에 0을 대입하였습니다.
👾트리스티의 답
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
// 원동균 / 11066 / 파일 합치기
"use strict"; const { memory } = require("console"); const ps = (function (process) { const readline = require("readline"); const rl = readline.createInterface({ input: process.stdin, output: process.stdout, }); let lines = []; let cursor = 0; rl.on("line", function (line) { lines.push(line); }); return { main(f) { f() .catch((err) => { console.error(err); process.exit(1); }) .finally(() => { rl.close(); }); }, use(name, f) { this[name] = f; }, readLine: async function readLine() { return new Promise((resolve) => { if (cursor < lines.length) { resolve(lines[cursor++]); } else { setTimeout(() => readLine().then((line) => { resolve(line); }) ); } }); }, async readArrayLine() { const line = await this.readLine(); return line.split(/\s/).map((t) => parseInt(t)); }, write(data) { process.stdout.write(data + ""); }, writeLine(data) { process.stdout.write((data === undefined ? "" : data) + "\n"); }, range(start, end, step = 1) { if (end === undefined) { end = start; start = 0; } return { [Symbol.iterator]: function* () { for (let i = start; i < end; i += step) { yield i; } }, }; }, }; })(process); ps.main(async () => { const result = []; const N = parseInt(await ps.readLine()); // 이 문제에서 dp를 직관적으로 사용하기 위해 index 0이 아니라 1부터 시작합니다. 따라서 501의 크기를 갖는 배열을 선언합니다. const dp = Array.from(Array(501), () => Array(501).fill(0)); const sum = Array.from(Array(501).fill(0)); for (let i = 0; i < N; i++) { const K = parseInt(await ps.readLine()); const novel = (await ps.readLine()) .split(" ") .map((element) => parseInt(element)); // 입력된 값의 누적합을 구합니다. for (let j = 1; j <= K; j++) { sum[j] = sum[j - 1] + novel[j - 1]; } result.push(combine(novel, K)); } for (const i of result) { console.log(i); } // 합치기 함수 // 최소 비용으로 소설을 합치기 위해서는 최소 비용의 부분합을 구해야 합니다. function combine(novel, K) { for (let i = 1; i < K; i++) { for (let j = 1; i + j <= K; j++) { dp[j][i + j] = Infinity; for (let k = j; k < i + j; k++) { dp[j][i + j] = Math.min( dp[j][i + j], dp[j][k] + dp[k + 1][i + j] + sum[i + j] - sum[j - 1] ); } } } return dp[1][K]; } }); |
cs |
※ 잘못된 정보가 있거나 수정사항이 있다면 댓글로 남겨주세요!