Cow Dance Show

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

14452번: Cow Dance Show

 

스테이지 크기가 k라고 했을 때, 소들이 어떻게 댄스 공연을 마치는지 시뮬레이션하는게 쉽지는 않다.

그냥 구현하라고 하면 매 시간마다 누가 끝났는지 확인하고, 그곳에 새로운 소들을 배치하면 된다.

하지만, 소가 공연하는 시간도 크고, 소들의 숫자도 만만치 않다.

 

어떻게 해야할까?

일단 시뮬레이션을 하면서 누가 끝났는지를 바로 알 수 있다면, 시간을 획기적으로 줄일 수 있을텐데라는

생각을 했다. 끝났다는 뜻은 대충 생각해보면 값이 가장 작다는 뜻이다.

흠.. 그럼 값이 작은 걸 한 번에 찾을 수 있는 자료구조는? 이라고 생각해보면.

바로 'heap'이라는 걸 알 수 있다. 힙 중에서소 'min heap'을 쓰면 되겠군.

 

근데 위에서 생각한대로 소들의 공연 시간을 힙에 그대로 넣어주면 될까?

그러면 시뮬레이션이 안된다. (현재 시간) + (해당 소의 공연 시간) 으로 넣어줘야지 빨리 끝나는지

늦게 끝나는지 확실히 알 수 있다. 즉, 소들의 끝나는 시간을 미리 구해서 힙에 넣어준다!

문제를 좀 더 쉽게 만들어준 조건이 하나 있었는데, 소들이 주어진 순서대로 들어간다는 것이다.

만약 소들을 재배치해서 최소 시간을 만들어라 라고 했다면, 아마 더 어려워졌을 것이다.

 

나머지는 parametric search를 통해서 문제가 원하는 값을 구하면 된다.

그렇게 구하라고 문제에서 아주 노골적으로 말하고 있다. (please determine the smallest possible value of K.)

이 말이 무조건 이런 방식으로 풀어라 라는 뜻은 절대 아니지만..

 

 

 

#include <iostream>
#include <algorithm>
#include <iterator>
#include <vector>
#include <string>
#include <string.h>
#include <queue>
#define endl    '\n'
#define FastIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
 
vector<int> cows;
int n, t;
 
int check(int support) {
    priority_queue<int, vector<int>, greater<int>> pq;
    int idx = 0;
    for(; idx < support; idx++)                    // 먼저 k개 소들을 힙에 넣어준다. 
        pq.push(cows[idx]);
 
    int cur_time = 0;                            // 현재 시간을 뜻한다.
    while (!pq.empty()) {
        cur_time = pq.top();
        while (!pq.empty() && cur_time == pq.top()) pq.pop();    // 현재 시간에 끝나는 소들을 모두 꺼내준다.
        while (pq.size() < support && idx < cows.size()) pq.push(cur_time + cows[idx++]);    // 남은 소들을 스테이지가 꽉 찰 때까지 채워준다.
    }
 
    return cur_time;
}
 
 
int main() {
    FastIO;
 
    cin >> n >> t;
    cows.resize(n);
    for (int i = 0; i < n; i++)
        cin >> cows[i];
 
 
 
    int l = -1, r = n;
    while (l + 1 < r) {
        int mid = (l + r) >> 1;
        if (check(mid) > t) l = mid;
        else r = mid;
    }
 
 
    cout << r << endl;
 
 
 
    return 0;
}