백준, 2805 나무자르기 javascript

백준, 2805 나무자르기

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

👨‍💻 문제 풀이

• 일반적인 이분탐색으로 접근하고, 조금만 수정해주면 되는 문제.
• 이분탐색으로 최종의 mid를 구하되, 중간에 구해진 값이 target 값보다 클 경우 (최댓값을 구하므로) answer값에 계속해서 재할당한다.

💻 제출한 코드

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

const [N, M] = input.shift().split(' ');
const trees = input[0].split(' ').map(Number).sort((a,b) => a-b);

function solve(arr, target) {
    let start = 0;
    let end = arr[arr.length-1];
    let answer = Number.MIN_SAFE_INTEGER;
    while(start <= end) {
        let mid = Math.floor((start + end)/2);
        let sum = 0;
        for(let x of arr) {
            if(x > mid) sum += x-mid;
        }

        if(sum >= target) {
            if(mid > answer) answer = mid; 
            // 최댓값 계속 구해주기.
          	// 이 부분을 제외하고는 일반적인 이분탐색 코드와 똑같다.
            start = mid + 1;
        } else {
            end = mid - 1;
        }
    }

    return answer;
}

console.log(solve(trees, M))

이번 문제를 풀면서,

• 이분탐색 공부를 하고 이분탐색을 활용하며 푼 문제.
• 낮은 정답률과 어색한 이분탐색에 괜히 이 문제를 굉장히 어려운 문제라고 생각했고, 덕분에 혼자서 머리를 돌면서 어렵게 생각했다. 😅
• 나중에 다시보니 생각보다 엄청 쉬운 로직이였고, 이 문제 덕분에 이분탐색 다시 공부하면서 좀 익숙해졌다.