[백준]2805번. 나무 자르기(JAVA)

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

---

문제

---

풀이

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

public class Main {


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

        st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        int[] height = new int[n];

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

        Arrays.sort(height);
        int start = 0;
        int end = height[n-1];
        int answer = 0;

        while (start <= end){
            int mid = (start + end) / 2;
            long sum = 0;

            for(int x : height){
                if(x > mid){
                    sum += x - mid;
                }
            }
            if(sum < m){
                end = mid -1;
            }else{
                start = mid + 1;
                answer = mid;
            }
        }

        System.out.println(answer);
    }
}

 

문제풀이를 위해 이분탐색을 사용했다.

초기 나무 높이 배열을 높이 순으로 정렬한 다음에 절단기의 높이를 중간값으로 설정한다.

이후에 (나무의 높이) - (절단기)를 해서 초과하는 값을 sum 변수에 저장하고 만약 이 값이 내가 원하는 높이보다 작다면 end를 낮춰 절단기의 높이가 더욱 낮아지게 한다.

반대로 크거나 같다면 내가 원하는 상황이 될 수 있기 때문에 start를 높이게 된다.

 

이분탐색을 사용해야한다라고 알고 시작한 문제이기 때문에 변수를 조금 헷갈려도 맞출 수 있었던 문제라고 생각된다.

조금 더 변수명 선정에 의미를 두는 연습을 해야 문제 풀이를 직관적으로 할 수 있을 것 같다.