[백준] 16564 히오스 프로게이머 - Java

 

 

문제 출저

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

16564번: 히오스 프로게이머

 

 

 

문제 풀이

총 N개의 케릭터의 level이 주어집니. k는 레벨을 올릴 수 있는 총량입니다. 이 때 k를 적절히 분배해여 최소값을 가장 높게 만드는게 이 문제의 요구사항 입니다.

 

저는 이분 탐색으로 문제를 풀었습니다.

최소 레벨을 탐색에 대상으로 하였습니다.

최소값은 주어진 레벨의 최소값으로 하였고 최댓값은 주어진 레벨에서 가장 큰 레벨에 k를 더한 값으로 했습니다. 

이분 탐색을 진행할 때 목표 레벨과 주어진 레벨의 차이를 구하고 모두 더합니다.

모두 더한 값이 k 이하면 조건을 충족하는 것 이므로 값을 키웠습니다. (s = mid + 1)

모두 더한 값이 k 보다 크면 조건을 충족 못하므로 값을 줄였습니다. (e = mid - 1)

이런 식으로 탐색을 진행하여 정답을 구했습니다.

 

 

 

소스 코드 

package baekjoon.backjoon9.day23;


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

/*
히오스 프로게이머
https://www.acmicpc.net/problem/16564
 */
public class B16564 {

    static int n, k;
    static long[] level;

    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());

        level = new long[n];

        long small = 1_000_000_000;
        long large = 1;

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

            small = Math.min(small, level[i]);
            large = Math.max(large, level[i]);
        }

        long s = small;
        long e = large + k;

        long answer = 0;

        while(s <= e) {
            long mid = (s+e)/2;

            if(check(mid)) {
               s = mid + 1;
               answer = mid;
            }
            else {
                e = mid - 1;
            }
        }

        System.out.println(answer);
    }

    public static boolean check(long number) {
        long result = 0;

        for(int i = 0; i < n; i++) {
            if(number > level[i]) {
                result += number - level[i];
            }
        }

        if(result <= k) {
            return true;
        }
        else {
            return false;
        }
    }

}