[취업준비일지] - 111

 

 

(1).백준 2805 나무 자르기는 일정 높이 이상을 전부 잘라버리고
남은 통나무들의 합이 일정 이상이면 만족하는 문제였다.

다만 환경을 생각하는 상근이(?)는 딱 목표치까지만 자르고 싶어 했고
높이는 무려 20억까지 올라가기 때문에
20억부터 1씩 내려올 수도 0부터 올라갈 수도 없는 문제였다.

이 문제를 해결하기 위해 이분탐색을 사용해야만 했고
수도 코드를 아래와 같이 작성했다.
//1.해당 높이에서 처리할 경우 나오는 결과 true/false boolean return function 만들기
//2.이분탐색 구현 후 전,후를 넣어 true/false 순으로 나오는 구간 적용하기
//3.해당 구간 높이 출력
//4.1개일 경우에도 true/false순 출력 확인 가능

의식의 흐름으로 따지자면 1과 2가 반대지만
기능적 구현의 순서는 1과 2의 순서로 진행이 맞기 때문에 저 순서로 구현했다.

현재 위치가 최적인 경우 한칸 더 높게 자를 경우에는 나무가 부족하기 때문에
현재 높이를 넣을 경우에는 true, +1의 높이에서는 false가 나오는 위치를 찾게 이분탐색을 구성했고
true, false를 판별해줄 함수는 나무를 모두 자른 다음
잘린 나무의 길이의 합이 목표치보다 많거나 같을 경우에 true 나머지는 false를 리턴하게 구성했다.

몇번 당한 기억이 있기 때문에
최저, 최고의 높이에서 생길 수 있는 문제에 대해 생각했지만
다행히도 정상 범위의 입력만 있었기 때문에
제일 높은 나무를 Math.max와 구조분해 할당으로 구한 다음
0~max-1을 범위로 구하도록 지정했다.
(max의 높이값은 더 높은 나무가 없어 잘린 나무의 합이 0이라 무조건 탈락이다)

const input = `4 7
20 15 10 17`.split('\n')

const [logAmount, logNeeded] = input[0].split(' ').map(Number)
const logArr = input[1].split(' ').map(Number)

const cutLogChecker = (height) => {
    let cuttedLogSum = 0
    for(let i = 0 ; i < logAmount ; i++){
        if(height < logArr[i]){
            cuttedLogSum += logArr[i] - height
        }
    }
    if(cuttedLogSum >= logNeeded) return true
    else return false
}

let left = 0
let right = Math.max(...logArr)-1

while (left <= right) {
    const middle = Math.floor((left+right)/2)
    const check1 = cutLogChecker(middle)
    const check2 = cutLogChecker(middle+1)
    if(check1 && !check2){
        console.log(middle)
        break
    }
    else if(check2){
        left = middle+1
    }
    else{
        right = middle-1
    }
}