백준 2805 나무자르기 - JAVA

문제 링크

---

https://www.acmicpc.net/problem/2805

 

문제 설명

---

 

입출력

---

 

코드

---

import java.util.*;
import java.io.*;
public 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[] tree = new int[N];
        long max = 0;
        long min = 1;
        long mid = 0;
        
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            tree[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max, tree[i]);
        }
        
        while(min <= max) {
            mid = (min + max) / 2;
            long count = 0;
            for (int i = 0; i < tree.length; i++) {
                if(mid < tree[i]) {
                    count += tree[i] - mid;
                }
            } 
            if (count < M) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        bw.write(String.valueOf(max));
        bw.flush();
    }
}

 

알고리즘 설명

---

해당 문제는 배열로만 이분탐색을 풀었던 분들에게는 생소한 문제였을것이라고 생각합니다. 해당문제는 순차검색으로 해결은 가능한 문제이지만, 이분탐색으로 시간을 효율적으로 줄일 수 있습니다. 먼저 자를 수 있는 최소값과 최대값을 설정해야 하는데, 최소값은 1, 최대값은 가장 긴 나무의 길이로 설정합니다. 이제 집에 가져갈 나무의 길이는 최소값과 최대값 사이에서 모두 구할 수 있기 때문에, 최소값과 최대값으로 mid값을 구해서 각 트리별로 길이가 mid값보다 큰 경우에만, 트리 길이 - mid값을 누적합하여 집에 가져갈 나무의 길이보다 작다면 max값을 mid + 1로 설정하고, 누적합이 집에 가져갈 나무의 길이보다 크다면 min값을 mid + 1로 설정합니다.

M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하여야 하기 때문에, max의 값을 출력합니다.

 

코드 해석

---

N(나무의 수)와 M(필요한 나무의 길이) 입력받고, N개의 나무 높이를 입력받아 tree[] 배열에 저장합니다. 가장 높은 나무 높이를 max로 설정하고 min <= max일때까지 이분탐색 루프를 실행합니다. 상한값을 찾는 문제이므로 종료된 루프에서 max를 받아 출력합니다.