BOJ - 1654 랜선 자르기

1. 문제 : 랜선 자르기

2. 문제 티어: 실버2

3. 문제 유형 : 이진 탐색

4. 문제 풀이 방법

=> 나무 자르기와 동일한 방식으로 이진 탐색으로 최적의 갯수를 찾는 것이 핵심이다.

1) 필요한 변수 값 입력 받음

2) 랜선 잘랐을 때 값을 얻을 수 있는 지 판단하는 함수 작성

3) 이진 탐색으로 최적의 갯수를 카운트하는 함수 작성

4) 결과 출력

 

5. 코드 

1) 필요한 변수 값 입력 받음

// 1. 필요한 값 입력 받음
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [N,M] = input[0].split(" ").map(Number);
let lengths = [];

for(let i=1;i<=N;i++){
    lengths.push(input[i]);
 }

 

2) 랜선 잘랐을 때 값을 얻을 수 있는 지 판단할 수 있는 함수 작성

// 2. canCut 함수 작성
function canCut(lengths, target, length) {
    let count = 0;
    for(let i of lengths) {
        count += Math.floor(i / length);
    }
    return count >= target; // true or false로 판별
}

 

3) 이진 탐색으로 최대 랜선 길이를 찾는 함수

function binarySearch(lengths, target){
    let low = 1;
    let high = Math.max(...lengths);
    let result = 0;
    
    while(low <= high) {
        let mid = Math.floor((low + high) / 2);
        if(canCut(lengths, target, mid)){
            result = mid;
            low = mid + 1;
        } else {
            high = mid - 1;
         }
    }
    return result;
 }

 

4) 결과 출력

console.log(binarySearch(lengths,M));