[백준 1654] 랜선 자르기
February 13, 2023
문제
https://www.acmicpc.net/problem/1654
아이디어
자르려는 랜선의 길이를 가지고 조정하면서 이진 탐색을 하면 되는 문제이다.
가장 긴 사이즈와 가장 짧은 사이즈의 중간 크기로 잘랐을 때 케이블이 부족하다면 랜선을 더 짧게 잘라야 한다.
반면에, 케이블이 남는다면 더 길게 잘라도 되므로 더 길게 잘랐을 때 케이블의 갯수가 어떻게 되는지를 확인하면 된다.
소스코드
// 입력 정제
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const [k, n] = input[0].split(" ").map(e => Number(e));
const cable = input.slice(1, k + 1).map(e => Number(e)).sort((a, b) => a - b);
// size로 랜선을 잘랐을 때 몇 개가 만들어지는지를 반환
function cutting(size) {
return cable.reduce((acc, value) => acc + Math.floor(value / size), 0);
}
// 문제
function solution() {
let start = 0;
let end = cable[cable.length - 1];
let result = 0;
while (start <= end) {
let mid = Math.floor((start + end) / 2);
let numOfCable = cutting(mid);
// 케이블이 부족하면 더 잘게 잘라야 한다.
if (numOfCable < n) end = mid - 1;
// 케이블이 넘치면 더 길게 잘라도 된다.
else {
start = mid + 1;
result = mid; // 현재 자른 크기가 가장 최적이었을 경우를 대비해서 현재 자른 크기를 기록해둔다.
}
}
console.log(result);
}
// 실행
solution();