백준 - 2805 나무 자르기 [이분 탐색]

 

2805번: 나무 자르기

 

1. 문제 요약

나무의 수 n, 가져가려고 하는 나무의 길이 m이 주어지고,

나무의 높이 수열이 주어진다.

자를 높이를 지정하면 해당 높이에 맞게 모든 나무가 잘리며, 지정한 높이 이하의 나무들은 잘리지 않는다.

m을 만족하면서 자를 수 있는 나무의 높이의 최솟값을 구하시오.

 

2. 접근 방법

• 자르는 높이 별로 얻을 수 있는 나무의 길이를 수열이라 생각하고 이분 탐색을 활용하여 풀면 쉽게 풀 수 있습니다.

• 빨간색이 배열의 인덱스, 파란색이 탐색할 배열이라 생각하고 이분 탐색을 사용합니다.

 

3. 파이썬

def solution(target, trees):
    s = 1
    e = max(trees)
    while s <= e:
        mid = (s+e) // 2
        wood = 0
        for tree in trees:
            if tree > mid:
                wood += tree - mid
        
        if wood >= target:
            s = mid + 1
        else: # wood < target
            e = mid - 1

    return e

 

4. 자바

private static int solution(int target, int[] trees) {
    int s = 1;
    int e = getMaxValue(trees);
    while (s <= e) {
        int mid = (s + e) / 2;
        long wood = 0;
        for (int tree : trees) {
            if (tree > mid) {
                wood += tree - mid;
            }
        }

        if (wood >= target) {
            s = mid + 1;
        } else {
            e = mid - 1;
        }
    }
    return e;
}

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/2805.%E2%80%85%EB%82%98%EB%AC%B4%E2%80%85%EC%9E%90%EB%A5%B4%EA%B8%B0