백준, 1654 랜선 자르기 javascript

백준, 1654 랜선 자르기

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

👨‍💻 문제 풀이

• 이분탐색을 이용해서 문제를 풀었다.
• 얼마전 풀었던 나무자르기 문제와, 최댓값을 구한다는 점에서 동일한 로직을 사용했다.

💻 제출한 코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [K, N] = input.shift().split(' ');
const lines = input.map(Number).sort((a,b) => a-b);
// 이분 탐색은 정렬된 배열에만 적용할 수 있음.
const target = +N;

let left = 0;
let right = lines[lines.length-1];

let answer = Number.MIN_SAFE_INTEGER;
while(left <= right) {
    let mid = Math.floor( (left + right)/2 );
    let lineNum = lines.reduce((acc, cur) => acc + Math.floor(cur/mid), 0);
    //  mid값에 따라서 구해지는 랜선의 갯수.

    if(lineNum >= target) {
        // 구해지는 랜선의 개수가 target보다 같거나 많은 경우
        if(mid > answer) answer = mid;
        // mid값 중 최댓값을 구할 것이기 때문에 추가한 로직.

        left = mid + 1;
        // 구해지는 랜선의 길이를 낮게해야함 -> 랜선을 나누는 길이를 높여줘야함. -> left를 증가시켜 줘야 함.
    } else {
        right = mid - 1;
    }
}

console.log(answer);

이번 문제를 풀면서,

• 이 문제도 나무자르기 문제와 같이 이상하게 정답률이 낮다.
• 근래서 정답률에 지레 겁먹고, 문제를 조금 미뤄놨는데...
• 나무자르기 문제와 아예 똑같은 로직을 공유하고 있었고, 굉장히 쉽게 풀었다.
• 정답률을 보고 문제를 너무 무서워 하지 말자.🥲