[JavaScript/이분탐색] 백준 실버 2 : 1654 - 랜선 자르기

https://www.acmicpc.net/problem/1654

1654번: 랜선 자르기

---

📌 작성한 코드 

// 1654
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [K, N] = input.shift().split(" ").map(Number);
const list = input.map(Number);

let start = 0;
let mid = Math.max(...list);
let end = mid;

let answer = 0;

while (true) {
    let count = 0;
    list.forEach((v) => {
        count += Math.floor(v / mid);
    });

    if (count < N) {
        let temp = mid;
        mid = Math.floor((mid - start) / 2) + start;
        end = temp;
    } else {
        if (answer < mid) answer = mid;
        else break;

        let temp = mid;
        mid = Math.floor((end - mid) / 2) + temp;
        start = temp;
    }
}

console.log(answer);

 

📌 설명 

랜선 K개를 잘라서 N개의 랜선을 만들어야 한다고 했을 때 가능한 최대 랜선 길이를 구하는 문제이다. 

가장 큰 랜선 길이를 기준으로 해서 이분 탐색을 적용해 가능한 최대 랜선 길이를 구할 수 있다.

 

이분 탐색을 통해 찾는 원리는 이러하다.

(1) 기준이 되는 랜선(mid)을 반으로 잘라서 해당 길이를 사용하면 몇개의 랜선을 만들 수 있는지 확인한다,

(2) 만들 수 있는 랜선의 개수가 N개 미만이면, 랜선의 길이를 다시 반으로 나눈 후에 다시 만들 수 있는 랜선의 개수를 확인한다.

(3) 만들 수 있는 랜선의 개수가 N개 이상이면, 가장 긴 랜선의 길이를 찾기 위해서 현재 랜선 길이와 (현재)가능한 가장 긴 랜선 길이의 중간 점을 랜선 길이로 해서 다시 N개의 랜선을 만들 수 있는지 확인한다. 

while (true) {
    let count = 0;
    list.forEach((v) => {
        count += Math.floor(v / mid);
    });

    if (count < N) { // N개 미만의 랜선 구해지면 반으로 자르기
        let temp = mid;
        mid = Math.floor((mid - start) / 2) + start;
        end = temp;
    } else { // N개 이상의 랜선 구해지면 최장 랜선 길이를 찾기 위해 더 긴 길이 가능한지 확인
        if (answer < mid) answer = mid; 
        else break; // answer 보다 길이가 작거나 같아지면 더 이상 탐색할 길이가 남지 않았다는 의미 

        let temp = mid;
        mid = Math.floor((end - mid) / 2) + temp;
        start = temp;
    }
}

 

✅ 성공