[ BOJ ][JAVA][16564] 히오스 프로게이머

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

16564번: 히오스 프로게이머

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	512 MB	880	415	303	46.977%

문제

성권이는 Heroes of the Storm 프로게이머 지망생이다.

이 게임에는 총 N개의 캐릭터가 있다. 그리고 현재 각 캐릭터의 레벨은 Xi이다. 성권이는 앞으로 게임이 끝날 때까지, 레벨을 최대 총합 K만큼 올릴 수 있다.

팀 목표레벨 T =min(Xi) (1 ≤ i ≤ N)라고 정의하면, 게임이 끝날 때까지 성권이가 달성할 수 있는 최대 팀 목표레벨 T는 무엇인가?

예를 들어, N = 3, X1= 10, X2= 20, X3= 15이고 K = 10일 때, X1을 7만큼 올리고 X3을 2만큼 올리면 최소 레벨 Xi는 17이 된다. 따라서 팀 목표레벨 T는 17이다. 이 경우처럼 레벨을 총합 K보다 적게 올릴 수도 있다.

입력

첫째 줄에는 캐릭터의 개수 N, 올릴 수 있는 레벨 총합 K가 주어진다. (1 ≤ N ≤1,000,000, 1 ≤ K ≤ 1,000,000,000)

다음 N개의 줄에는 현재 각 캐릭터의 레벨이 X1, X2, X3, ... , Xn 으로 주어진다. (1 ≤ Xi ≤ 1,000,000,000)

출력

가능한 최대 팀 목표레벨 T를 출력한다.

예제 입력 1

3 10
10
20
15

예제 출력 1

17

코드

/**
 * BOJ 16564 히오스 프로게이머 : Silver 1
 * 이분탐색
 */
import java.io.*;
import java.util.*;

public class p16564 {
    static int n, k, answer;
    static int[] lev;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        k = Integer.parseInt(st.nextToken());
        answer = 0;

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

        int min = Integer.MAX_VALUE;
        int max = 0;
        for (int i = 0; i < n; i++) {
            if (min > lev[i]) {
                min = lev[i];
                continue;
            }
            if (max < lev[i]) {
                max = lev[i];
            }
        }

        int lo = min;
        int hi = max + k;
        while (lo <= hi) {
            int mid = (lo + hi) / 2;

            if (check(mid)) {
                answer = Math.max(answer, mid);
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
        System.out.println(answer);
    }

    /**
     * 
     * @param num 팀의 최소 목표 레벨
     * @return 달성가능 여부
     */
    static boolean check(int num) {
        // 사용할 수 있는 레벨업 한계는 k

        int useLevel = 0;
        // 초기 num=20 :: 주어진 k로 최소 20을 만들 수 있어?
        for (int i = 0; i < n; i++) {
            if (num <= lev[i]) continue;

            useLevel += num - lev[i];
            if (useLevel > k) return false;
        }

        return true;
    }
}