Q 13702 이상한 술집

💡 문제 요약 및 분석

은상이와 친구들은 이상한 술집에서 막걸리를 나눠 먹으려 한다. 이 술집에서 막걸리를 주문하면 주전자 용량은 같지만 막걸리의 용량은 랜덤하다. 각자 주문한 막걸리를 똑같은 양으로 나눠 먹으려고 할 때, 최대한 많은 양의 막걸리를 분배할 수 있는 용량 ml 를 계산하자.

💡 알고리즘 설계

✅ 핵심 아이디어 : 이분 탐색으로 해결 가능.

1. 입력

   • 표준입력으로 int N, int K 저장한다.
   • 표준입력으로 막걸리 용량을 int[N] kettles 배열에 저장한다. 이 때 주어지는 용량의 최대값 max 를 저장한다.

2. 연산

   • left = 1, right = max
   • 중간값 mid를 계산한다. mid = (left + right) / 2
   • count += kettles[i] / mid mid 용량으로 막걸리를 나눠 먹을 때 총 몇 개로 나눌 수 있는지 계산한다.
   • 다음의 경우의 수가 있을 수 있다. count >= K : left = mid + 1; result = mid; count < K : right = mid - 1

3. 출력

   • result 변수를 출력한다.

💡 코드

public class Main {

    static int read() throws Exception {
        int c = 0, n = 0;
        while ((c = System.in.read()) > 47) n = (n << 3) + (n << 1) + (c & 15);
        return n;
    }

    public static void main(String[] args) throws Exception {
        int N = read();
        int K = read();
        long[] kettles = new long[N];
        long max = 0;
        for (int i = 0; i < N; i++) {
            int input = read();
            kettles[i] = input;
            max = Math.max(max, input);
        }

        long left = 1;
        long right = max;
        long result = 0;

        while (left <= right) {
            long mid = (left + right) / 2;
            int count = 0;
            for (int i = 0; i < N; i++) {
                count += kettles[i] / mid;
            }
            if (count >= K) {
                left = mid + 1;
                result = mid;
            } else if (count < K) {
                right = mid - 1;
            }
        }
        System.out.println(result);
    }

}

💡 시간 복잡도, 공간 복잡도

시간 복잡도	공간 복잡도
O(n * log max)	O(n)

💡 느낀점 및 기억할 정보

코딩테스트에서 무조건 “long” 을 쓰는 것이 좋은 전략일까?

당연하겠지만 필요할 때 “long” 을 쓰는 것이 더 좋은 전략이다. 그렇지만 예상치 못한 오버플로우 때문에 틀리는 경우가 있으니 미리 long 을 사용하는 습관을 갖는 것도 좋을 듯 한데, 이건 자신만의 룰을 갖고 접근하는 것이 좋을 것 같다.

1. 기본적으로는 int 를 사용하자.
2. “누적합”, “곱셈”, “이분 탐색”, “2^31 - 1 을 넘는 범위” 가 나온다면 long 을 사용하자.