[백준] 2805 나무자르기

www.acmicpc.net/problem/2805

2805번: 나무 자르기

2021-01-13

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main2805 {
    public static int N;
    public static long M, answer, arr[];
 
    public static boolean check(long num) {
        long sum = 0;
        for(int i = 0; i < N; i++) {
            if(arr[i] - num > 0) sum += (arr[i] - num);
        }
        if(sum >= M ) {
            if(num >= answer) answer = num;
            return true;
        }
        return false;
    }
 
    public static void solve() {
        long left = 0;
        long right = arr[N-1];
        while(left <= right) {
            long mid = (left + right) / 2;
            if(check(mid)) left = mid+1;
            else right = mid-1;
        }
    }
    public static void main(String[] args) throws Exception {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Long.parseLong(st.nextToken());
 
        arr = new long[N];
        answer = 0;
 
        st = new StringTokenizer(bf.readLine());
        for(int i = 0; i < N; i++) {
            arr[i] = Long.parseLong(st.nextToken());
        }
        Arrays.sort(arr);
        solve();
 
        System.out.println(answer);
    }
}

#문제풀이
파라매트릭 서치로 푸는 문제이다.

1. arr에 입력값을 받고, sort 해주었다 .

2. left는 0, rigth는 arr의 가장 큰 값으로 설정해두었다. 

3. left와 right의 mid 값을 구한다. 만약 그 값에서 arr의 값을 뺀 값들을 합쳤을 때 M보다 크고, 기본 answer 값 보다 mid 값이 더 크다면 answer는 mid이 된다.

4. 위에서 sum의 값이 M보다 큰 경우에는 left의 값을 mid+1로 옮겨 체크 안 한 부분까지 체크하게 하고, false인 경우에는 right 값을 mid-1로 줄여서 작은 값부터 체크할 수 있게 한다.