[백준] 16564번 : 히오스 프로게이머

히오스 프로게이머

---

해결 방법

이분탐색 문제를 해결하는데 있어서 참고할 자료를 찾았다.

https://www.acmicpc.net/blog/view/109

해당 자료를 참고하니 이분탐색 문제에 있어서 이해하기 쉬웠다.

이번 문제는 시작 지점, 끝 지점을 잡는게 핵심인 문제였다.
시작 지점과 끝 지점은 항상 정답의 범위를 나타낼 수 있게 해야한다.

이번 문제에서는 각 캐릭터의 레벨이 모두 동일할 때를 생각해서 level[n-1]+k 가 최대 값이 되어야 했다.

이 부분만 조심한다면 다른 이분탐색 문제와 크게 다르지 않게 해결 가능했다!

이분탐색 문제를 많이 풀어보니 이젠 비슷한 문제가 나오면 응용해서 해결할 정도가 되었다!
역시 반복이 가장 빠르고, 확실히 이해할 수 있는 것 같다~

---

코드

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));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int n = Integer.parseInt(st.nextToken());
        long k = Long.parseLong(st.nextToken());
        long[] level = new long[n];
        for(int i=0;i<n;i++){
            level[i] = Long.parseLong(br.readLine());
        }

        Arrays.sort(level);

        System.out.println(binarySearch(k,0,level[n-1]+k,level));

    }
    public static long binarySearch(long m,long min,long max,long[] arr){
        long result = 0;
        while(min<=max){
            long mid = (min+max)/2;
            long count = 0;
            for(long i : arr){
                if(mid-i>0)
                    count += mid-i;
            }
            if(count>m){
                max = mid - 1;
            }
            else{
                result = mid;
                min = mid + 1;
            }
        }

        return result;
    }
}