BOJ - 2805 나무 자르기

1. 문제 : https://www.acmicpc.net/problem/2805

2. 문제 유형 : 이진 탐색

3. 문제 티어 : 실버2

4. 문제 해결 방법
=> 이진 탐색 문제이다. 특정 높이까지 오기 전까지 계속 반복해야 하는 문제이기 때문에 로직을 아래와 같이 잡았다.

1) 필요한 변수들 입력 받음 (N, M , arr)
 * N = 나무 수 ,  M = 나무 길이 , arr = 나무 높이가 들어가 있는 배열 

2) 총 나무 길이를 구할 수 있는 함수 작성

3) 이진 탐색으로 최적의 절단기 높이를 찾는 함수 작성 

4) console.log로 출력

 

5. 코드

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

// 입력값 받는 부분
const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [N,M] = input[0].split(" ").map(Number); // N = 나무 수 , M = 나무 길이
let arr = input[1].split(" ").map(Number) // 나무 높이 배열

 

2) 총 나무 길이를 구할 수 있는 함수 작성

 // 2. 총 가져갈 수 있는 나무 길이 계산하는 함수 작성
 function canCut(treeHeights , target, height) {
     let total = 0;
     for(let tree of treeHeights) {
         if(tree > height) total += tree- height;
         }
         return total >= target; // total이 더 크면 true 반환
 }

 

= 각 나무를 주어진 절단기 높이 height로 잘랐을 때 얻을 수 있는 총 나무 길이를 계산하기 위함이다.

= 총 나무 길이가 target 이상인지 확인 후 true or false를 반환한다. 

= true : 총 나무 길이가 target 이상이다. (목표 달성 가능)

= false : 총 나무 길이가 target 보다 작다. (목표 달성 불가능)

= 나무를 height 만큼 자른 후 남은 길이가 있을 시만 total에 저장함.

 

3) 이진 검색으로 최적의 절단기 높이 찾는 함수 작성

function binarySearch(treeHeights, target) {
    let low = 0;
    let high = Math.max(...treeHeights);
    let result = 0;
    
    while(low <= high) {
        // 중간 값 설정 후 중간 값 기준으로 탐색
        let mid = Math.floor((low + high) / 2);
        // 만약 true 즉, 중간값 기준으로 높이 절단 했을 때 total 길이가 있을 시
        if(canCut(treeHeights, target, mid)) {
           // 결괏값은 중간값이 됨
           result = mid;
           // 최솟값을 더 증가 시켜서 범위 변경
           low = mid + 1;
         } else {
              // 그렇지 않을 시 최댓값을 줄여서 범위 변경
              high = mid - 1;
         }
       }
       // 결괏값 반환
       return result;
 }

 

4) 결과 출력

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

 

5) 시간 복잡도 

이진 탐색의 반복 횟수 O(log M)와 canCut 함수의 시간 복잡도 O(N) 결합하면 : 
O(N log M)