[BOJ] 13702번 : 이상한 술집

문제

프로그래밍 대회 전날, 은상과 친구들은 이상한 술집에 모였다. 이 술집에서 막걸리를 시키면 주전자의 용량은 똑같았으나 안에 들어 있는 막걸리 용량은 랜덤이다. 즉 한 번 주문에 막걸리 용량이 802ml 이기도 1002ml가 나오기도 한다. 은상은 막걸리 N 주전자를 주문하고, 자신을 포함한 친구들 K명에게 막걸리를 똑같은 양으로 나눠주려고 한다. 그런데 은상과 친구들은 다른 주전자의 막걸리가 섞이는 것이 싫어서, 분배 후 주전자에 막걸리가 조금 남아 있다면 그냥 막걸리를 버리기로 한다. (즉, 한 번 주문한 막걸리에 남은 것을 모아서 친구들에게 다시 주는 경우는 없다. 예를 들어 5명이 3 주전자를 주문하여 1002, 802, 705 ml의 막걸리가 각 주전자에 담겨져 나왔고, 이것을 401ml로 동등하게 나눴을 경우 각각 주전자에서 200ml, 0m, 304ml 만큼은 버린다.) 이럴 때 K명에게 최대한의 많은 양의 막걸리를 분배할 수 있는 용량 ml는 무엇인지 출력해주세요.

- 시간 제한 : 1초
- 메모리 제한 : 512MB

입력

첫째 줄에는 은상이가 주문한 막걸리 주전자의 개수 N, 그리고 은상이를 포함한 친구들의 수 K가 주어진다. 둘째 줄부터 N개의 줄에 차례로 주전자의 용량이 주어진다. N은 10000이하의 정수이고, K는 1,000,000이하의 정수이다. 막걸리의 용량은 2^31 - 1 보다 작거나 같은 자연수 또는 0이다. 단, 항상 N ≤ K 이다. 즉, 주전자의 개수가 사람 수보다 많을 수는 없다.

출력

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

접근 방법

막걸리의 최대 용량이 2^31 - 1이므로 모든 경우를 살펴볼 경우 시간 제한내에 문제를 해결할 수 없으므로 이진 탐색으로 문제를 해결해야 합니다. 주전자에서 막걸리를 나누고 남은 막걸리는 버리기 때문에 나눌 양이 주어졌을 때, 몇개의 컵에 나눌 수 있는지 구하는 함수를 아래와 같이 구현할 수 있습니다.

/**
 * @param amount 막걸리를 나눠 컵에 따를 양
 * @return 막걸리를 amount만큼 따를 때 공평히 나눌 수 있는 컵의 수
 */
static int getCupCount(int amount) {
    int count = 0;

    for (int i : kettles) {
        count += i / amount;
    }

    return count;
}

위의 함수와 이진 탐색을 이용하여 아래와 같이 문제를 해결할 수 있습니다.

코드

import java.lang.*;
import java.io.*;
import java.util.*;

public class Main {

    static int n, k;
    static int[] kettles;
    static int result;

    public static void main(String[] args) {
        input();
        func();
        System.out.println(result);
    }

    static void input() {
        Scanner sc = new Scanner(System.in);

        n = sc.nextInt();
        k = sc.nextInt();
        kettles = new int[n];

        for (int i = 0; i < n; ++i) {
            kettles[i] = sc.nextInt();
        }

        sc.close();
    }

    static void func() {
        // 막걸리의 최대 용량이 2^31 - 1이므로 long으로 해야한다.
        long left = 1;
        long right = Integer.MAX_VALUE;

        // 이진탐색으로 답을 찾는다.
        while (left <= right) {
            int mid = (int)((left + right) / 2);

            // 나눌 양이 mid일 때, 모두에게 막걸리를 나눠줄 수 있으면
            // 더 많이 나눠도 모두에게 줄 수 있는지 탐색해본다.
            if (k <= getCupCount(mid)) {
                left = mid + 1;
                
            // 모두에게 나눠줄 수 없으면, 나눌 양을 더 적게한다.
            } else {
                right = mid - 1;
            }
        }

        result = (int)right;
    }

    /**
     * @param amount 막걸리를 나눠 컵에 따를 양
     * @return 막걸리를 amount만큼 따를 때 공평히 나눌 수 있는 컵의 수
     */
    static int getCupCount(int amount) {
        int count = 0;

        for (int i : kettles) {
            count += i / amount;
        }

        return count;
    }
}

주의할 점

막걸리 용량의 최대가 2^32 - 1이므로 이진 탐색을 할 때, left와 right를 long으로 하는 것이 좋습니다. 그렇지 않으면 오버플로우가 일어나서 문제를 해결하지 못하게 됩니다.