백준 13702 JAVA : 이상한 술집

문제

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

13702번: 이상한 술집

 

풀이 예상

각 주전자에서 몇으로 나눌지 조합해서 구하는 것은 K가 100만을 넘으므로 불가능 하다고 생각했다.

막걸리의 나눌 ml 수를 구하고 해당 수로 막걸리를 나눴을 때 몫의 합이 K 이상이면 된다고 생각해서 막걸리의 ml를 이분탐색으로 구하는 방법을 선택했다.

 

풀이방법 (접근 방법 & 시간복잡도)

1. 막걸리를 배열에 넣고, 총 막걸리 ml 를 구한다.

2. start = 0, end = 총 막걸리 ml 로 두고 이분 탐색을 시작한다. (start가 0이 될 수 있음에 주의 해야한다.)

3. mid 값으로 막걸리들을 나누고, 몫을 count한다.

4. count가 K보다 작다면 ml수를 줄여야 하기 때문에 end값을 갱신하고, 그렇지 않다면 start값을 갱신한다.

5. ml가 0일 수 있기 때문에 0처리를 해준다.

 

시간복잡도 => O(N * log total) 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        long[] alcol = new long[N];
        long total = 0; //총 막걸리 용량

        for (int i = 0; i < N; i++) {
            alcol[i] = Long.parseLong(br.readLine());
            total += alcol[i];
        }

        //이분탐색으로 1~total 확인

        long start = 0;
        long end = total;

        while (start <= end) {
            long mid = (start + end)/2;

            long count = 0;
            if(mid != 0) {
                for (int i = 0; i < N; i++) {
                    count += alcol[i]/mid;
                }
            }else {
                count = K;
            }

            if(count < K) {
                //나눠줄 사람 수가 적은 경우 -> 용량 더 적게
                end = mid-1;
            }else {
                //나눠줄사람 수가 같거나 높은 경우 -> 용량 더 크게
                start = mid+1;
            }

        }
        System.out.println(end);

    }
}

 

결과