백준 (BOJ) 16564 히오스 프로게이머 java

 

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

16564번: 히오스 프로게이머

 

 

정형화된 이분 탐색만 풀었다면 이런 문제는 또 다른 시야를 갖게 해주는 것 같다.

 

중간에 sum 값을 long 범위로 설정해야 한다는 점은,

 

조금만 생각해보면 알 수 있(는데 왜 나는 처음에 안 그랬는지 모르겠)다.

 

 

 

역시 이분탐색 문제답게 low와 high 설정이 중요하다.

 

사실 high를 10억으로 맞춰놓고 풀어도 문제 없이 정답이 되는 것 같긴 하다. (피셜입니다.)

 

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

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];

        for(int i=0; i<N; ++i){
            arr[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(arr);

        int l = arr[0]; // 제일 적은 값은 아무 것도 더해지지 않은 제일 낮은 레벨
        int h = arr[0] + K; // 제일 큰 값은 제일 낮은 레벨이 K의 모든 값을 취하는 경우 (이후의 [1], [2], ...는 더해줄 필요가 없을 때)

        int mid, ans = arr[0];
        while (l <= h){
            mid = (l + h) >> 1;

            // 가지고 있는 K의 값 범위 내에서 기준 값 mid에 맞춰 모두 나눠줄 수 있는가
            long sum = 0;

            int diff;
            for(int i=0; i < N; ++i){
                diff = mid - arr[i];
                if(0 < diff){
                    sum += diff;
                }
            }

            // 남은 차(diff)의 값을 더한 sum 값이 K의 범위 안에 들어올 때 --> 답이 될 수 있음!
            if(sum <= K){
                ans = Math.max(ans, mid);
                l = mid + 1;
            }
            else{
                h = mid - 1;
            }
        }

        System.out.print(ans);
    }
}