[USACO] Cow Dance Show

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

---

잘못된 부분을 발견하시면, 댓글 남겨주시면 매우 감사하겠습니다.

1) 결정 문제 : 현재 K값에 대한 T값이 Tmax보다 큰가 작은가?
2) 결정 문제의 분포 : F F F ... F T ... T T T
3) 초깃값 : lo = 0, hi = 10000이상의 아무 값

이분 탐색에서 가장 어려운 부분이 결정 문제의 답을 찾는 check() 함수를 작성하는 것 같습니다.

이 문제의 결정 문제에 대한 답을 찾기 위해서는, 무대에 K마리의 소만 올라갈 수 있을 때, 모든 소가 Tmax이전에 무대에 올랐다가 내려갈 수 있는지 판별해야 합니다.

무대에는 K마리의 소가 올라갈 수 있고, 한 마리씩 정해진 시간만큼 춤을 추고 나면 내려가고, 다음 소가 올라는 것을 반복합니다.
무대에는 소들이 올랐다 내렸다하고, 무대에서 내려가는 시간이 가장 빠른 소부터 처리해야하기 때문에, 이를 쉽게 처리하기 위해 우선순위 큐를 사용했습니다. 우선순위 큐로는 각각의 소들이 무대에서 내려가는 시간을 관리할 겁니다.
우선순위 큐에 담기는 값을 계산하기 위해 현재 시간을 담을 변수(time) 또한 필요합니다.

문제의 예제를 가지고 설명하겠습니다.
d[] = { 4, 7, 8, 6, 4 }, Tmax = 8, time = 0, PriorityQueue(pq) = {}

1) k = 3인 경우
1. 처음 3마리가 무대에서 내려가기까지는 자기에게 부여된 시간만큼이 걸릴겁니다. 따라서 pq = { 4, 7, 8 } 입니다.
2. 4번째 소가 무대에 오르기 위해서는 현재 무대에 있는 소들 중 한 마리가 내려가야 하기 때문에, 가장 짧은 시간 4를 가진 소가 내려갈겁니다. 이 소가 내려가기 위해서는 시간이 4가 지나야 하기 때문에 현재 시간 time = 4가 되고, 다음 소는 현재 시간부터 6초 동안 춤을 춘 뒤 무대에서 내려가기 때문에 pq에는 4 + 6 = 10이 담겨야합니다. 하지만 10 > Tmax이기 때문에 이 소는 Tmax전에 무대에서 내려갈 수 없습니다. 따라서 false를 return합니다.

2) k = 4인 경우
1. pq = { 4, 7, 8, 6 }
2. 한 소가 무대에서 내려가기까지 걸리는 시간 = 4 -> time = 4, 다음 무대에 올라올 소가 무대에서 내려가기까지 걸리는 시간 = 4 + 4 <= Tmax -> pq = { 7, 8, 6, 8 }
3. 현재 pq에 있는 모든 소는 Tmax이전에 무대에서 내려가기 때문에 true를 return합니다.

---

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

public class Main {

    static int n, t;
    static int[] d = new int[10005];

    private static boolean check(int mid){
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int time = 0;
        for(int i=0; i<n; i++){
            if(!pq.isEmpty() && pq.size() == mid) time = pq.poll();
            if(time + d[i] > t) return false;
            pq.add(time + d[i]);
        }
        return true;
    }

    public static void main(String[] args) throws IOException {

        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        StringTokenizer st = new StringTokenizer(bf.readLine());
        n = Integer.parseInt(st.nextToken());
        t = Integer.parseInt(st.nextToken());
        for(int i=0; i<n; i++) d[i] = Integer.parseInt(bf.readLine());

        int lo = 0, hi = 10005;
        while(lo + 1 < hi){
            int mid = (lo + hi) / 2;
            if(check(mid)) hi = mid;
            else lo = mid;
        }

        System.out.println(hi);
    }
}

check()함수의 시간 복잡도 : O(NlogK), 이분 탐색 시간 복잡도 : O(logN)
총 시간 복잡도 : O(Nlog^2N)