코테 - 나무자르기(2805)

⭐문제 : https://www.acmicpc.net/problem/2805

❤️ 접근법 : 이진탐색

1. 나무 중 가장 높은 나무의 높이를 구하여 max 변수에 저장합니다.
2. min과 max의 선을 조절하며 mid를 조절 -> 최대 높이 h에 이진탐색으로 접근
3. min은 잘라낼 나무의 최소 높이, max는 잘라낼 나무의 최대 높이이다. 즉 while문은 min<max 일때까지만 진행된다.
4. 이진 탐색을 통해 min과 max의 중간값 mid를 구하고, 이 높이로 나무를 잘랐을 때 얻을 수 있는 나무의 길이 합을 구한다.
5. 탐색트리를 돌리며 "나무높이 - 평균" 의 값을 계산해 총합에 더함
6. while 문이 종료가 되면, min이 max보다 크다는 의미이다. 즉 해당 케이스는 최대의 M을 구할 수 없다는 의미

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int M, max=0;
    public static void main(String[] args) throws IOException {
        int [] array =  init();
        int min=0;
        while (min<max){
            int mid = (min+max)/2;
            long sum=0;
            for(int target : array){
                if(target-mid>0) sum+=target-mid;
            }
            if (sum>=M) min=mid+1; //너무 많이 잘랐다는 뜻. 즉 하한선을 높여야함.
            else max = mid;// 너무 적게 잘랐다는 뜻. 상한선을 낮춰야 함.
        }
        System.out.println(min - 1);
    }

    public static int [] init() throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        int[] array = new int[N];
        st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++){
            array[i] = Integer.parseInt(st.nextToken());
            max = Math.max(max,array[i]);
        }
        return array;
    }

}

🖥️케이스 분석

나무 높이 배열: [20, 15, 10, 17]

• 첫 번째 이진 탐색
  min: 0, max: 20, mid: 10
  잘린 나무 길이 합: (20-10) + (15-10) + (10-10) + (17-10) = 10 + 5 + 0 + 7 = 22
  22는 M보다 크므로 min = mid + 1 = 11

• 두 번째 이진 탐색
  min: 11, max: 20, mid: 15
  잘린 나무 길이 합: (20-15) + (15-15) + (10-15) + (17-15) = 5 + 0 + 0 + 2 = 7
  7은 M과 같으므로 min = mid + 1 = 16

• 세 번째 이진 탐색
  min: 16, max: 20, mid: 18
  잘린 나무 길이 합: (20-18) + (15-18) + (10-18) + (17-18) = 2 + 0 + 0 + 0 = 2
  2는 M보다 작으므로 max = mid = 18

• 네 번째 이진 탐색
  min: 16, max: 18, mid: 17
  잘린 나무 길이 합: (20-17) + (15-17) + (10-17) + (17-17) = 3 + 0 + 0 + 0 = 3
  3은 M보다 작으므로 max = mid = 17

• 다섯 번째 이진 탐색
  min: 16, max: 17, mid: 16
  잘린 나무 길이 합: (20-16) + (15-16) + (10-16) + (17-16) = 4 + 0 + 0 + 1 = 5
  5는 M보다 작으므로 max = mid = 16