[백준/Java] 13702번 : 이상한 술집

✏️ 문제 분석

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

K명의 사람들에게 N개의 주전자로 막걸리를 최대한 균등하게 나누어줄 때,

막걸리를 나눠줄 수 있는 최대용량을 구하는 문제이다.

✏️ 구현 아이디어

막걸리의 용량이 최대 2^31-1보다 작거나 같은 자연수가 될 수 있기 때문에

막걸리의 최대 용량을 찾을 때 이분 탐색을 사용하는 게 적절해보인다.

 

start=1, end=2^31-1로 설정하고

N개의 주전자에서 현재 막걸리 용량으로 모든 사람에게 균등하게 나눠줄 수 있다면

막걸리 용량 탐색 범위를 큰 쪽으로,

균등하게 나눠줄 수 없다면 탐색 범위를 작은 쪽으로 조절한다.

✏️ 알고리즘

이분 탐색 알고리즘

✏️ 시간 복잡도

이분 탐색 O(logN)마다 주전자 수 N만큼 방문하며 사람 수를 계산해야 하므로

전체 시간 복잡도는 O(log2^31-1)*10,000

따라서 시간 내에 연산 가능하다.

✏️ 코드 설계

1. 입력 받기
2. 이분 탐색 
   1. 탐색 범위: 1~2^31-1
   2. mid가 조건을 만족한다면 탐색 범위를 오른쪽으로, 아니면 왼쪽으로
   3. 조건 확인 : 각 주전자 용량에서 mid로 나눈 몫을 합하여 총 합이 사람 수와 일치하는지 확인
3. 최대 용량 출력

✏️ 정답 코드

import java.io.*;

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

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

        long[] makgeolliList = new long[N];
        long maxMakgeolli = 0;

        for (int i = 0; i < N; i++) {
            makgeolliList[i] = Long.parseLong(br.readLine());
            maxMakgeolli = Math.max(maxMakgeolli, makgeolliList[i]);
        }

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

        while (left <= right) {
            long mid = (left + right) / 2;
            int count = 0;

            for (long makgeolli : makgeolliList) {
                count += makgeolli / mid;
            }

            if (count >= K) {
                result = mid;
                left = mid + 1; 
            } else {
                right = mid - 1; 
            }
        }

        System.out.println(result);
        br.close();
    }
}