문제
제목부터 웃음벨,,, 그르다 김가놈ㅋㅋㅋㅋㅋ
일단 이 문제에서는 김밥을 꼬다리 Kcm만큼 양쪽을 자른 다음에 김밥을 썬다. 근데 문제는 2Kcm보다 짧으면 한쪽만 자른다는 것이다.
Pcm로 만든 각각의 김밥 조각들이 M개 나오게 되는데, 이 M이 주어지면 P가 나올 수 있는 가장 큰 수를 구해야 한다.
예제를 보자.
n(손질해야 하는 김밥) : 3, k(꼬다리 길이) : 6, M(김밥 조각의 최소 개수) : 4이고, 김밥은 각각 20, 10, 3cm이다.
첫 번째 김밥의 경우는 양옆 꼬다리를 제거하고 8cm가 남았고, 두번째 김밥의 경우는 한 쪽만 꼬다리를 잘라 4cm가 남았다. 세번째 김밥은 꼬다리 길이보다 작아서 폐기되었다.
그럼 이 8cm와 4cm를 가지고 최대 4개의 조각을 가지면서 최대한의 길이를 가져야 한다. 그러기 위해서는 2cm로 나눠야만 m만큼의 조각이 나온다. 무턱대고 4cm로 자르거나 하면 최소 김밥 개수를 맞추지 않기 때문에 이를 맞추는 방법을 생각해야 한다.
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
.readFileSync(INPUT_FILE)
.toString()
.trim()
.split("\n");
const [n, k, m] = inputs[0].split(" ").map(Number);
const kimbabs = inputs.slice(1).map(Number);
let kimbabWithoutCcodari = kimbabs.map((kb) => {
if (kb >= 2 * k) return kb - 2 * k;
if (kb > k) return kb - k;
return 0;
});
const minP = Math.floor(
kimbabWithoutCcodari.reduce((acc, curr) => acc + curr, 0) / m
);
for (let i = minP; i > 0; i--) {
let accM = 0;
kimbabWithoutCcodari.forEach((bab) => {
if (bab <= minP) return;
accM += Math.floor(bab / i);
});
if (accM >= m) {
console.log(i);
process.exit(0);
}
}
console.log(-1);
처음에는 그냥 선형적으로 문제를 풀려 했다. 꼬다리 없는 김밥을 미리 배열로 새롭게 만든 다음에 모든 길이를 합치고, 최소 개수로 나누면 이때부터 루프를 시작해도 되겠다고 생각했다. 이보다 더 큰 값은 나올 수 없기 때문이다. 그렇게 한 뒤에는 루프문으로 최대부터 하나씩 내려가면서 조건에 맞는 경우 바로 루프문을 빠져 나오려 했다.
하지만 이렇게 된 알고리즘의 문제는
- 베스트케이스를 찾지 못할 경우 끝까지 감
- 길이가 0인 김밥을 배열에 그대로 냅둬서 시간이 더 오래 걸리게 됨 과 같은 문제가 있었다.
결국 알고리즘 분류를 보게 되었고, 이러한 문제를 해결하기 위해서는 이분 탐색을 통해 풀어야 한다는 것을 알았다.
const INPUT_FILE = process.platform === "linux" ? "/dev/stdin" : "./inputs.txt";
const inputs = require("fs")
.readFileSync(INPUT_FILE)
.toString()
.trim()
.split("\n");
const [n, k, m] = inputs[0].split(" ").map(Number);
const kimbabs = [];
for (let i = 1; i < n + 1; i++) {
const kb = +inputs[i];
if (kb > 2 * k) {
kimbabs.push(kb - 2 * k);
} else if (2 * k > kb && kb > k) {
kimbabs.push(kb - k);
}
}
if (kimbabs.length === 0) {
console.log(-1);
process.exit(0);
}
let result = -1;
let left = 1;
let right = Math.max(...kimbabs);
while (left <= right) {
let mid = Math.floor((left + right) / 2);
let count = kimbabs.reduce((acc, L) => acc + Math.floor(L / mid), 0);
if (count >= m) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
console.log(result);
따라서 기존 김밥들을 map으로 길이를 바꾸는 것이 아니라 새 배열에 하나씩 Push해주는 방식으로 바꾸었고, 이분탐색을 통해 김밥들 중 가장 긴 값에서부터 시작해서 조건에 맞는 김밥이 나오는지 검사하여 탐색했다.
번외로 이 문제를 풀 때, 잠깐 백준의 채점 서버가 잘못되는 일이 있어 어떤 언어로 해도 틀렸거나 컴파일 오류가 나왔다는 등 바로 막혔었다.
백퍼 로직에 문제는 없다고 생각하면서 몇시간동안 계속 고쳤는데 너무 이상해서 백준 메인페이지에 가보니 다들 비슷한 문제를 겪고 있었다…
결론: 계속 틀리면 내가 아니라 세상을 탓하자(?)
