[백준] 16564 - 히오스 프로그래머

 

 

이분탐색 알고리즘 문제!

 

이분탐색 문제를 풀 떄 가장 먼저 찾아야 하는 조건은, 범위를 특정할 수 있는 최댓값과 최솟값이다.

문제의 조건에 따라

3 10
10
20
15

 

입력에서 10 이하의 수를 분배하였을 때 나올 수 있는 가장 높은 값은 30, 낮은 값은 10이 된다.

따라서 이진탐색 함수에서

min = levels[0] (정렬 기준)

max= levels[N-1] + K 로 설정하여 구할 수 있다.

 

 

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

 

목표 레벨을 mid 값으로 설정한 후, 목표 레벨이 되기 위해 더해야 하는 레벨 수를 count 변수에 저장한다.

count 변수보다 target 값이 큰 경우 max 값을 목표레벨 - 1 로 설정한다.

count 변수보다 target 값이 작거나 같은 경우 mid 값을 result로 저장하고, min 값을 목표 레벨 + 1 로 설정한다.

 

 

 

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

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

        int K = Integer.parseInt(input[1]);
        int N = Integer.parseInt(input[0]);
        int[] levels = new int[N];
        for (int i = 0; i < levels.length; i++) {
            levels[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(levels);
        System.out.println(binarySearch(levels, K, levels[0], levels[N - 1] + K));

    }


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

}

 

전체 코드