백준 13702 - 이상한 술집 (자바 - 이분탐색)

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

13702번: 이상한 술집

 

* 문제 요약

프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막거리를 시키면 주전자의 용량은 똑같았으나 안에 들어있는 막걸리 용량은 랜덤이다.

즉, 한 번 주문에 막걸리 용량이 802ml 이기도 1002ml 가 나오기도 한다. 은상은 막걸리 N 주전자를 주문하고, 자신을 포함한 친구들 K명에게 막걸리를 똑같은 양으로 나눠주려고 한다.

그런데 은상과 친구들은 다른 주전자의 막걸리가 섞이는 것이 싫어서, 분배 후 주전자에 막걸리가 조금 남아있다면 그냥 막거리를 버리기로 한다.

(즉, 한 번 주문한 막걸리에 남은 것을 모아서 친구들에게 다시 주는 경우는 없다. 예를 들어 5명이 3 주전자를 주문하여 1002, 802, 705ml 의 막걸리가 각 주전자에 담겨져 나왔고, 이것을 401ml 로 동등하게 나눴을 경우 각각 주전자에서 200ml, 0ml, 304ml 만큼은 버린다.) 이럴 때 K명에게 최대한 많은 양의 막걸리를 분배할 수 있는 용량 ml는 무엇인지 출력해주세요.

 

* 입력

첫째 줄에는 은상이가 주문한 막걸리 주전자의 갯수 N, 그리고 은상이를 포함한 친구들의 수 K가 주어진다. 

둘째 줄부터 N개의 줄에 차례로 주전자의 용량이 주어진다. N은 10,000 이하의 정수이고, K는 1,000,000 이하의 정수이다.

막걸리의 용량은 2^31 - 1 보다 작거나 같은 자연수 또는 0이다. 단, 항상 N <= K 이다. 즉, 주전자의 갯수가 사람 수보다 많을 수는 없다.

 

* 출력

첫째 줄에 K명에게 나눠줄 수 있는 최대의 막걸리 용량 ml 를 출력한다.

 

* 예시

 

* 해결 과정

전형적인 매개변수 탐색 문제, 문제에서 제시한 조건을 만족하는 값들 중 최대값을 구해줘야 한다.

즉, 친구 K명에게 나눠줄 수 있는 막걸리의 양을 이분탐색으로 찾아가는 동시에, 그 중 최대값을 구해야 한다.

1. start 를 0, end 를 입력받은 막걸리의 양들 중 최대값으로 초기화한다.

2. start <= end 조건을 만족하는 동안 다음의 로직으로 반복을 수행한다.

  - mid 변수를 (start + end) / 2 값으로 초기화한다.

  - mid 값을 대상으로 check(long mid) 메소드를 수행한다.

    - mid 값을 기준으로 각 막걸리의 양을 나눠서 나온 몫을 합산한다.

    - 합산한 값이 친구들의 숫자 K보다 크거나 같을 경우 true 를 리턴해준다.

    - 합산한 값이 친구들의 숫자 K보다 작을 경우 false 를 리턴해준다.

  - check(long mid) 메소드 수행 결과 true 를 리턴받았을 경우 result 변수를 현재 mid 값으로 초기화 해주고 start 를 mid + 1 로 초기화하여 다음 반복에서 mid 값이 더 커지는 방향으로 범위를 줄여준다.

  - check(long mid) 메소드 수행 결과 false 를 리턴받았을 경우 end 를 mid - 1 로 초기화하여 다음 반복에서 mid 값이 더 작아지는 방향으로 범위를 줄여준다.

3. 반복문이 끝나고 나면 result 를 출력해준다.

 

* 코드

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

public class Main {

    static int[] alcohol = null;
    static int K = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] inputArray = br.readLine().split(" ");
        int N = Integer.parseInt(inputArray[0]);
        K = Integer.parseInt(inputArray[1]);

        alcohol = new int[N];

        for (int i = 0; i < N; i++) {
            alcohol[i] = Integer.parseInt(br.readLine());
        }

        long start = 0;
        long end = (long) Arrays.stream(alcohol).max().getAsInt();
        long result = 0;

        if (start + 1 >= end) { // 시작부터 끝나는 경우, 즉 end 값이 곧 정답인 경우
            bw.write(end + "\n");
        } else {
            while (start <= end) {
                long mid = (start + end) / 2;

                if (check(mid)) {
                    result = mid;
                    start = mid + 1;
                } else {
                    end = mid - 1;
                }
            }

            bw.write(result + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }

    private static boolean check(long mid) {

        long result = 0;

        for (int i = 0; i < alcohol.length; i++) {
            long div = alcohol[i] / mid;
            result += div;
        }

        if (result >= K)
            return true;
        else
            return false;
    }
}

 

입력받은 막걸리들 중 가장 양이 많은 것을 기준으로 최대 범위를 잡고, 범위 안의 중간값으로 주전자들에 들어있는 막걸리들을 나눴을 때 친구들에게 모두 나누어 줄 수 있는지 없는지에 따라 범위를 줄여가며 친구들에게 가장 많은 양의 막거리를 나눠줄 수 있는 경우를 찾았으므로 이분탐색 문제에 해당된다.