[백준] 13702. 이상한 술집

문제 링크

[백준] 13702. 이상한 술집

풀이 과정

이분 탐색 문제입니다.

int low = 0, high = max;

while (low <= high) {
    int mid = (low + high) / 2;
    int cnt = 0;

    for (int num : arr) cnt += num / mid;

    if (cnt >= K) low = mid + 1;
    else high = mid - 1;
}

low 를 0, high 를 입력된 막걸리의 최대 용량으로 설정한 뒤, 이분 탐색을 실행합니다. 이분 탐색 동작 과정은 다음과 같습니다.

1. 중간값 mid 를 구합니다.
2. 막걸리 배열을 돌면서, 각각의 막걸리를 mid 로 나눴을 때, 몇 명한테 나눠줄 수 있는지 cnt 를 계산합니다.
   • cnt 가 K 이상이면, 남는 막거리가 존재하므로 low 를 좁힌 뒤 다시 이분 탐색을 진행합니다.
   • cnt 가 K 미만이라면, 막걸리가 부족하므로 high 를 좁혀 다시 이분 탐색을 진행합니다.
3. low 가 high 를 넘어서는 순간의 high 값이 K 명에게 나눠줄 수 있는 막걸리의 최대 용량이 됩니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int K = sc.nextInt();
        int[] arr = new int[N];
        int max = 0;

        for (int i = 0; i < N; i++) {
            arr[i] = sc.nextInt();
            max = Math.max(max, arr[i]);
        }

        int low = 0, high = max;

        while (low <= high) {
            int mid = (low + high) / 2;
            int cnt = 0;

            for (int num : arr) cnt += num / mid;

            if (cnt >= K) low = mid + 1;
            else high = mid - 1;
        }

        System.out.println(high);
    }
}