[C++] 백준 14452번: Cow Dance Show

문제 링크

14452번: Cow Dance Show

문제 요약

여러 소들이 동시에 무대에서 춤을 추는데, 소들에게는 무대에 오르는 순서가 정해져 있다. 각 소들이 춤을 추는 시간이 주어질 때, 모든 소가 춤을 T 시간 안에 마칠 수 있는, 무대 크기의 최솟값을 구해야 한다.

접근 방법

매개변수 탐색으로 무대의 크기를 정해야 합니다. low는 1, high는 모든 소의 수로 정해줍니다. 그리고 이분탐색을 하면서 k를 찾아주면 됩니다.

현재 무대 크기로 모든 소들이 춤을 출 수 있는지 판단하기 위해서는 우선순위 큐를 이용해야 합니다. 이 판단을 위해서 별도의 함수를 정의 해주었습니다.

초기에 우선순위 큐에 현재 무대 크기만큼의 소들을 집어 넣습니다. 그리고 그 다음 소부터 무대에 오를 수 있도록 하는데, 현재 우선순위큐에서 최솟값(가장 춤이 빨리 끝나는 소)을 꺼내서, 이번에 무대에 올라갈 소가 춤 출 시간을 더해서 다시 삽입해주면 됩니다. 이 과정에서 제한 시간인 T를 넘기는지 확인하고, T를 넘긴다면 false, 넘기지 않는다면 true를 반환해줍니다.

매개 변수 탐색에서 실수만 하지 않으면 간단하게 풀리는 문제입니다.

코드

#include <bits/stdc++.h>

using namespace std;

int n, t;
vector<int> v;

bool check(int k) {
	priority_queue<int, vector<int>, greater<int>> pq;

	for (int i = 0; i < k; i++)
		pq.push(v[i]);

	for (int i = k; i < n; i++) {
		int tmp = pq.top();
		pq.pop();

		if (tmp + v[i] > t)
			return false;
		else
			pq.push(tmp + v[i]);
	}

	return true;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> t;
	v.resize(n);
	for (auto& i : v) cin >> i;

	int low = 1, high = n, ans = 0;
	while (low <= high) {
		int mid = (low + high) / 2;

		if (check(mid)) {
			high = mid - 1;
			ans = mid;
		}
		else {
			low = mid + 1;
		}
	}

	cout << ans << '\n';
	return 0;
}