BOJ 14452 - Cow Dance Show (usaco silver, 이분탐색)

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

 

이분탐색할때 mid값이 문제 조건에 맞는 지 판단하는 isPossible 함수를 짤 때, multiset이나 priority_queue를 이용하고 싶었으나 구현을 못해서 vector로 구현했더니 시간초과가 났던 문제.. Barking dog님의 코드를 참고했습니다.

https://github.com/blisstoner/BOJ/blob/master/14452.cpp

 

 

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;

int n, t;
int d[10000];

bool isPossible(int k) {
	multiset<int> ms;
	int tot = k, time = 0;

	for (int i = 0; i < k; i++) ms.insert(d[i]);

	while (tot < n && time < 1000001) {
		time = *ms.begin();
		ms.erase(ms.begin());
		ms.insert(time + d[tot++]);
	}

	time = *prev(ms.end());
	return time <= t ? true : false;
}

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

	cin >> n >> t;

	for (int i = 0; i < n; i++)	cin >> d[i];
	
	int lo = 1, hi = n;
	while (lo < hi) {
		int mid = (lo + hi) / 2;
		if (isPossible(mid)) hi = mid;
		else lo = mid + 1;
	}

	cout << lo << '\n';
}

 

처음에 짰던 코드.

bool isPossible(int k) {
	vector<int> ms;
	queue<int> q = d;
	int time = 0;

	for (int i = 0; i < k; i++) {
		if (!q.empty()) {
			ms.push_back(q.front()); 
			q.pop();
		}
	}
	sort(ms.begin(), ms.end());

	while (!ms.empty()) {
		int temp = *ms.begin(); 
		ms.erase(ms.begin());
		time += temp;
		for (auto iter = ms.begin(); iter!=ms.end(); iter++ ) 
			(*iter) -= temp;

		if (!q.empty()) {
			ms.push_back(q.front());
			q.pop();
			sort(ms.begin(), ms.end());
		}
	}

	return time <= t ? true : false;
}

새로 추가하는 요소에 time을 더해주고 time갱신하면 되는것을.. 새로운 요소가 들어올때마다 multiset에 있는 요소들의 시간을 조정해서 시간초과가 났다.