백준 2805번 : 나무 자르기 자바

 

 

🧫 문제 분석

 

✔️ 출처

나무 자르기 실버 2

 

📖 문제

 

이진 탐색 문제로

나무를 잘랐을 때 적어도 M 미터의 나무를 집에 가져가기 위해 설정할 수 있는 높이의 최댓값을 구해야한다.

 

여기서 적어도 M미터의 의미는

절단 높이가 최댓값을 가질때까지 찾되 적어도 M 미터 이상은 가져가야겠다는 의미이다.

 

예를 들어

1~Int Max 의 절반으로 잘랐을 때 M미터를 넘겼다면 

좀 더 그 위에를 잘랐을 때 M 미터 이상이면서 자르는 높이를 높여서 나무를 덜 자를 수 있는 경우가 있다.

 

 

푸는 방식

 

이진 탐색을 하되

M 미터 이상이면 높이를 더 높여서 탐색해본다.

 

주의할 점

자르는 높이 이하인 나무들은 무시해야한다.

 

 

반례 하나를 남기겠다.

2 7
3 9
정답 : 2
오답 : 0

 

밑에 처럼 짜면 오답이 나온다. 

이유를 생각해보자

if (sum == m) {
    max = Math.max(max, mid);
    
} else if (sum > m) {
    binarySearch(mid + 1, right); 
    
} else {
    binarySearch(left, mid - 1);
}

 

 

중간 값을 구한 후 잘랐을 때 나무가 m미터를 초과해서 나왔다 치자

자르는 높이를 더 올린다. 

그런데 높인 위치가 몇몇 나무들의 높이보다 높은 경우가 발생한 것이다.

따라서 sum < m 이 되어버린다. 

 

Test 결과

위의 반례를 통해서 보면

높이가 2일 때 나무는 8미터를 얻는다. 하지만 sum > m 이기에 

다시 한번 3 , 3으로 호출해버리고, mid = 3으로 6미터의 나무를 얻었지만 

m = 7 이므로 left, mid - 1 로 왼쪽 부분을 호출하려하지만 left <= right 조건에 걸려 재귀는 종료된다.

 

 

 

---

🔅 문제 풀이

import java.io.*;
import java.util.*;

public class Main {

    static long max = 0;
    static int[] trees;
    static int m;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // 절단기에 설정할 수 있는 높이는 양의 정수 또는 0
        // 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값
        int n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());
        trees = new int[n];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        // M의 높이는 20억 이하
        binarySearch(1, Integer.MAX_VALUE);
        
        bw.write(max + "");
        bw.flush();
        bw.close();
    }

    private static void binarySearch(long left, long right) {

        if (left <= right) {
            long sum = 0;
            long mid = (left + right) / 2;

            for (int i = 0; i < trees.length; i++) {
                // 자르는 높이보다 작은 나무는 무시
                if (trees[i] - mid > 0) {
                    sum +=trees[i] - mid;
                }
            }

            // 나무를 m미터 보다 많이 얻었다면 자르는 높이를 더 높여서 환경보호 (*ㅅ*)
            if (sum >= m) {
                max = Math.max(max, mid);
                binarySearch(mid + 1, right); // 자르는 높이를 높여서 최소한의 m미터 이상만 가져가기 위해 탐색

                // 자르는 높이가 너무 높기에 높이를 낮춘다.
            } else if (sum < m) {
                binarySearch(left, mid - 1);
            }

        }

    }


}

 

 

 

2년전 질의 응답에서 나온 반례가 M이 100억일때 인데 

문제에서는 M이 20억까지라고 되어있어서 k를 int로 그냥 냅뒀다. 

 

 

❗ 오답노트 / 필요한 지식

1.  사실 문제 이해가 잘 안됐다. 환경 보호를 위해 m미터 이상?...? 뭔소리지 싶었는데 직접 로직을 따라 생각해보니 m 이상이면 자르는 높이를 올리는게 맞았다...
2. 이진탐색 연습!