[BOJ 13702] 이상한 술집 (Java, 매개변수 탐색)

 

 

---

문제 링크

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

13702번: 이상한 술집

---

풀이

- 이진탐색(매개변수 탐색) 문제 

- 시간복잡도 O(NlogN)

- long 타입 변수를 사용해야 하는 경우 있음

 

뒤집은 문제

용량(ml) 을 정했을 때, 친구(K)명에 막걸리를 골고루 분배 가능한가 ? 이때 용량(ml)는 최대인가?

 

부등호 헷갈리는 경우

주전자(N) 1개 이고 그 안에 21억ml가 담겨 있고, 친구(K) 100만명 있을 때

- 1000ml 로 나눌 경우 주전자에 10억 ml가 남고 친구 모두 분배 가능 ( 최대값을 찾기 위해 L 증가)

- 2000ml 로 나눌 경우 주전자에 1억ml 남고 친구 모두 분배 가능 (최대값을 찾기 위해 L 증가)

- 3000ml 로 나눌 경우 친구 모두 분배 불가 (기준 ml를 줄이기 위해 R을 감소)

 

---

 

제출 코드

- R 의 범위를 주어진 막거리 용량 중 최대값으로 지정할 경우 런타임 에러 발생(/by zero)하여 Integer.MAX_VALUE 지정

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

public class Main {
    static int N, K;
    static long[] drink;

    static void input() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 주문한 막걸리 주전자 개수 (최대 1만이하)
        K = Integer.parseInt(st.nextToken()); // 친구들의 수 (100만이하)

        drink = new long[N];
        for(int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            drink[i] = Long.parseLong(st.nextToken());
        }
    }

    static boolean isValid(long ml) {
        long cnt = 0;
        for(long d : drink) {
            cnt += (d / ml);
        }

        return cnt >= K;
    }

    static void pro() {
        long L = 0, R = Integer.MAX_VALUE, ans = 0;
        while(L <= R) {
            long mid = (L + R) / 2;
            if(isValid(mid)) { //최대 용량을 찾으므로 조건 성립시 L을 증가
                L = mid + 1;
                ans = mid;
            } else {
                R = mid - 1;
            }
        }

        System.out.println(ans);
    }

    public static void main(String[] args) throws Exception {
        input();
        pro();
    }
}