1. 문제
여름 휴가를 떠나기 위해 용돈이 필요했던 광우는 H택배 상하차 아르바이트를 지원 했다. 광우는 평소에 운동을 하지않아 힘쓰는 데에 자신이 없었지만, 머리 하나 만큼은 비상해 택배가 내려오는 레일의 순서를 조작해서 최소한의 무게만 들 수 있게 일을 하려고 한다.
레일은 N개이며, 각각의 레일은 Ni 무게 전용 레일로 주어진다. (같은 무게의 레일은 주어지지 않는다.) 레일의 순서가 정해지면 택배 바구니 무게(M)를 넘어가기 전까지 택배 바구니에 택배를 담아 들고 옮겨야 한다. 레일 순서대로 택배를 담되, 바구니 무게를 초과하지 않은 만큼 담아서 이동하게 되면 1번 일한 것으로 쳐준다. (단, 택배는 순서대로 담아야 하므로 레일의 순서를 건너 뛰어 담을 수는 없다)
총 K번 일을 하는데 최소한의 무게로 일을 할 수 있게 광우를 도와주는 프로그램을 만들어 보자.
제약조건
3 ≤ N ≤ 10
max(Ni) < M ≤ 50
1 ≤ K ≤ 50
1 ≤ Ni ≤ 50
입력형식
첫째 줄에는 레일의 개수 N, 택배 바구니의 무게 M, 일의 시행 횟수 K가 주어진다. 그 다음 줄에는 Ni개의 택배 레일의 전용 무게가 주어진다.
(택배 바구니는 무조건 택배보다 작은 경우는 없다.)
출력형식
출력으로는 광우가 일 해야하는 최소한의 택배 무게를 출력한다.
입력예제1
5 20 4
5 8 10 19 7출력예제1
54
레일의 개수가 5개이고 택배 바구니의 무게를 20, 일을 시행해야 하는 횟수를 4번 이라고 했을 때, 레일의 순서가 | 5 | 8 | 10 | 19 | 7 | 이 된다면 총 4번 수행 했을 때 답은 62가 된다.
1번 (5+8)
2번 (5+8) + (10)
3번 (5+8) + (10) + (19)
4번 (5+8) + (10) + (19) + (7+5+8) = 62
하지만 최적의 순서는 | 5 | 10 | 8 | 19 | 7 | 이 된다.
1번 (5+10)
2번 (5+10) + (8)
3번 (5+10) + (8) + (19)
4번 (5+10) + (8) + (19) + (7+5) = 54
입력예제2
9 25 50
1 21 2 22 3 23 4 24 107722. 풀이
2.1. 틀린 코드(순열 사용)
제약 조건에 N의 최댓값이 10이므로 무작정 순열로 풀어보려고 헀다.
- 순열을 구하는 함수를 따로 만들어서 모든 경우의 수를
rail_arr에 저장했다. for문과while문을 사용하여 각 경우의 수 별로 택배 무게를 구한 후, 최소값이라면 최소값을 갱신해 줬다.
전체 코드는 아래와 같다.
// 시간초과 발생한 코드 //
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let array = [];
// 순열 구하기
const getPermutations = function (arr, selectNumber) {
const results = [];
if (selectNumber === 1) return arr.map((e) => [e]);
arr.forEach((fixed, index, origin) => {
const rest = [...origin.slice(0, index), ...origin.slice(index + 1)];
const permutations = getPermutations(rest, selectNumber - 1);
const attached = permutations.map((permutation) => [fixed, ...permutation]);
results.push(...attached);
});
return results;
};
rl.on("line", (line) => {
array.push(line.split(" ").map(Number));
}).on("close", () => {
// [레일의 개수, 택배 바구니 무게, 일의 시행 횟수]
const [rails, basket_weight, works] = array[0];
let rail_weight = array[1];
// 순열로 모든 경우의 수 구하기
let rail_arr = getPermutations(rail_weight, rails);
let min_weight = 50 * 50; // 택배 무게를 큰 수로 저장
// 모든 경우의 수의 택배 무게를 구하여 최솟값으로 min_weight 갱신
for (let i = 0; i < rail_arr.length; i++) {
let array = rail_arr[i];
let cnt = 0;
let weight_sum = 0;
let basket = array[0];
let idx = 1;
while (cnt !== works) {
if (basket + array[idx] <= basket_weight) {
basket += array[idx];
idx = (idx + 1) % rails;
} else {
weight_sum += basket;
basket = 0;
cnt++;
}
}
if (weight_sum < min_weight) min_weight = weight_sum;
}
console.log(min_weight);
process.exit();
});하지만 이렇게 풀었더니 입력예제1은 통과했지만, 입력예제2는 시간제한을 초과했다는 결과가 나왔다.
2.2. 통과한 코드(브루트포스, 재귀 사용)
따라서 순열이 사용하지 말고, 브루트포스 접근 방식으로 코드를 수정했다.
simulate(array, basket_weight, works)array: 레일의 순서basket_weight: 택배 바구니 무게works: 일의 시행 횟수- 레일의 순서(
array)로 일했을 때 총 택배 무게(weight_sum)를 반환하는 함수
permute(arr, l, r, basket_weight, works)arr: 현재까지의 순열을 포함하는 배열l: 현재 단계에서 고려해야 할 시작 인덱스r: 배열의 마지막 인덱스basket_weight: 택배 바구니의 무게works: 일의 시행 횟수- 재귀적으로 배열의 모든 순열을 생성하고 각 순열에 대한 시뮬레이션 결과를 계산하는 함수
// 통과한 코드 //
const readline = require("readline");
const rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
});
let array = [];
// 해당 레일 순서대로 일했을 때 최소 무게 구하기
function simulate(array, basket_weight, works) {
let weight_sum = 0; // 총 택배 무게
let basket = 0; // 현재 시점 바구니 무게 합
let idx = 0;
for (let cnt = 0; cnt < works; cnt++) {
// 현재 시점 바구니 무게가 꽉 찰 때까지
while (basket + array[idx] <= basket_weight) {
basket += array[idx];
idx = (idx + 1) % array.length;
}
weight_sum += basket;
basket = 0; // 현재 시점 바구니 무게 reset
}
return weight_sum;
}
// 레일의 순서 바꿔가며 가능한 모든 조합 시도하기
function permute(arr, l, r, basket_weight, works) {
// 최소 무게를 아주 큰 값으로 초기화
let min_weight = 50 * 50 * 50;
// l과 r이 같으면 arr은 완성된 순열이므로 시뮬레이션 실행
if (l === r)
min_weight = Math.min(min_weight, simulate(arr, basket_weight, works));
else {
// l부터 r까지의 모든 원소를 순회
for (let i = l; i <= r; i++) {
// 순열의 다음 단계로
[arr[l], arr[i]] = [arr[i], arr[l]];
// 재귀 호출을 통해 다음 원소로 이동
min_weight = Math.min(
min_weight,
permute([...arr], l + 1, r, basket_weight, works)
);
// 원래 상태로 복구 (백트래킹)
[arr[l], arr[i]] = [arr[i], arr[l]];
}
}
return min_weight;
}
rl.on("line", (line) => {
array.push(line.split(" ").map(Number));
}).on("close", () => {
// [레일의 개수, 택배 바구니 무게, 일의 시행 횟수]
const [rails, basket_weight, works] = array[0];
let rail_weight = array[1];
let min_weight = permute(rail_weight, 0, rails - 1, basket_weight, works);
console.log(min_weight);
process.exit();
});이렇게 풀면 입력예제뿐만 아니라 문제를 통과할 수 있다.
브루트포스의 개념을 알고 있긴 했지만 재귀로 푸는 것은 아직 익숙치가 않다.
알고리즘 연습의 필요성을 느낀 문제다.
참고
