[Java] 백준(실버-2) 2805번 - 나무 자르기

문제 풀이

---

이 문제는 이분 탐색(이진 탐색) 알고리즘을 알고 있다면 풀 수 있다.

아이디어 도출

이분탐색 진행할 때, Upper Bound 방식으로 진행하였다. 이로 인해, 원하는 탐색값의 +1이 되기에 실제 원하는 가져갈 수 있는 나무의 최대 높이값은 찾아낸 값에서 -1이 된 값이라고 볼 수 있다.

나무를 최소한으로 자를 때, 예외를 방지하기 위해 Lower Bound가 아닌 Upper Bound를 사용했다.

1. min과 max를 이용해 중간 높이를 구한다.
2. 모든 나무에 중간 높이만큼을 잘라낸 나무의 길이(sum)를 M과 비교한다.
3. sum이 M보다 작으면 자르는 높이가 높다는 것이므로 상한높이를 mid로 낮춰준다.
4. sum이 M보다 크다면 자르는 높이가 낮다는 것이므로 하한높이를 mid+1하여 높여준다.
5. min이 max와 같거나 커지면 while 순회를 종료한다.
6. (max-1) 값이 M미터를 가져갈 수 있는 최대 높이가 된다.

위 아이디어를 토대로 문제 풀이를 위해 작성한 코드는 아래와 같다.

작성코드

---

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

class Main {

    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());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int[] trees = new int[N];

        // 나무의 하한높이 min, 상한높이 max 초기화
        int min = 0;
        int max = 0;

        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {;
            trees[i] = Integer.parseInt(st.nextToken());
            // 나무들 중 최대 높이를 구해 max에 저장
            max = Math.max(max, trees[i]);
        }

        // ** 이분탐색 진행(Upper Bound)
        while(min < max) {
            int mid = (max + min) / 2;
            // 또한 단일 나무의 길이가 최대 1,000,000,000 (10억) 이기 때문에 
            // int 타입이 아닌 long 타입으로 선언했다.
            long sum = 0;
            for(int tree : trees) {
                // 자르는 높이(mid)보다 나무의 높이가 더 낮은 경우에는 음수 값이 나오는데, 음수값은 sum에 합산하지 않는다.
                if((tree-mid) > 0) {
                    sum += (tree - mid);
                }
            }
            // 잘린 길이가 M보다 작다는 것은 자르는 위치가 높다는 것이므로 상한높이(max)를 낮춰준다.
            if(sum < M) {
                max = mid;
            } 
            // 잘린 길이가 M보다 크다는 것은 자르는 위치가 낮다는 것이므로 하한높이(min)을 높여준다.
            else {
                min = mid + 1;
            }
        }
        // max-1의 값이 M만큼 나무를 잘라 가져갈 수 있는 최대 높이이다.
        bw.write((max-1)+"\n");
        bw.close();
        br.close();
    }
}

출처

---

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.