[BOJ 14452] Cow Dance Show

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

14452번: Cow Dance Show

 

- 문제 요약

 

소들은 무대에서 발레 공연을 합니다. 무대의 크기는 K, 소의 수는 N이고 소들은 무대에 오르는 순서가 정해져 있습니다. N개의 줄에 소들이 춤을 추는 시간이 주어질 때, 모든 소가 T시간 안에 공연을 마무리할 수 있는 최소 무대 크기를 구하세요.

 

 

- 알고리즘 정리

 

이분탐색으로 무대의 크기 k를 찾아주는데, 이 때 모든 소가 T시간 안에 공연을 마칠 수 있도록 우선순위 큐를 활용해 줍니다. 각 소의 공연 시간을 우선순위 큐에 넣어서 오름차순으로 정렬해 주고 top을 꺼낸 다음 공연할 차례인 소의 공연 시간을 더해서 다시 우선순위 큐에 넣어줍니다. 이 과정을 계속 반복하다 보면 K가 T라는 조건에 부합한 지를 확인할 수 있습니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

int n,t;
vector<int>v;

bool f(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 w=pq.top();
		pq.pop();
		if(w+v[i]>t){
			return false;
		}
		else{
			pq.push(w+v[i]);
		}
	}
	return true;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>t;
	for(int i=0;i<n;i++){
	    int w;
		cin>>w;
		v.push_back(w);
	}
	int l=1,h=n,result=0;
	while(l<=h){
		int mid=(l+h)/2;
		if(f(mid)){
			h=mid-1;
			result=mid;
		}
		else{
			l=mid+1;
		}
	}
	cout<<result;
}

코드 제출 결과