[BOJ] 백준 14452. Cow Dance Show (Gold III)

백준 잔디 채우려고 G4..G2 티어 중 랜덤하게 뽑아본 문제.

문제는 아래와 같다.

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

14452번: Cow Dance Show

여기서 제일 중요한 점!

소 순서는 1~N번 순서대로 춤을 춘다!

T초 내에 모든 소들이 순서대로 춤을 추게 하려면 한번에 몇 마리의 소들이 춤을 출 수 있게 무대 사이즈를 만들어야 하는지 구하는 문제이다.

 

근데 순서 보장이 안돼있는 문제였어도 재밌었을 듯 하다.

sort한 후, 순서대로 더하다가 값이 T가 넘으면 답을 1 더하는 그리디적인 풀이로 낚을 수 있기 때문이다. 처음엔 그런 문제인 줄 알고, 꽤나 어렵게 생각했는데... 알고보니 어렵지 않은 문제였다.

---

의식의 흐름 및 해설

일단 T가 고정돼있고, 이 상태에서 K의 최솟값을 구하려고 하니, 엄청 큰 수는 딱히 없더라도 매개변수 탐색으로 시간복잡도를 줄이면 좋아보인다. (그리고 어차피 그리디나 스위핑으로 k를 구할 수도 없다. 또, O(n^2)은 시간초과이다.)

 

여기서, 순서가 고정돼있기 때문에 priority_queue로 최소에다가 d[i]를 더해주는 방식으로 갱신하면서, 이 때의 최댓값이 T를 넘는지 비교하면서 탐색하면 된다.

 

 

만약, 순서가 고정이 안돼있다면?

순서 고정 안돼있다고 sort후 순서대로 더하면서 구현하려는 오답을 도출해낼 수 있을텐데,

아래 데이터를 생각해봤으면 좋겠다.

5 8
2 3 5 6 7
ans: 3	// 원래 문제의 정답은 5.
wrong: 4

이 경우는 역순으로 정렬한 후에, priority_queue를 이용해주면 된다.

그러면 (큰 값 + 작은 값)이 만나면서 값이 평균에 가까워지기 때문에 max_value는 작아지기 때문이다.

Harmonic_lemma를 떠올리면 좋을 듯?

 

아무튼 이 문제는 이정도로 어렵진 않으니까 이 경우는 패스하자.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string>
#include <unordered_map>
#include <unordered_set>
#define all(v) (v).begin(), (v).end()
#define press(v) (v).erase(unique(all(v)), (v).end())
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
const int MAX = 1e6 + 11;
const int INF = 0x3f3f3f3f;
const ll LNF = 1e16;
const int MOD = 1e9 + 7;
int N, T, a[MAX];
int solve(int s, int e) {
	int ans = e;
	while (s <= e) {
		int mid = (s + e) / 2;
		int ret = 0;
		priority_queue<int, vector<int>, greater<int>> pq;
		for (int i = 0; i < mid; i++) {
			ret = max(ret, a[i]);
			pq.push(a[i]);
		}
		for (int i = mid; i < N; i++) {
			int n = pq.top();
			pq.pop();
			pq.push(n + a[i]);
			ret = max(ret, n + a[i]);
		}
		if (ret <= T) {
			ans = mid;
			e = mid - 1;
		}
		else
			s = mid + 1;
	}
	return ans;
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin >> N >> T;
	for (int i = 0; i < N; i++) {
		cin >> a[i];
	}
	cout << solve(1, N);
}

---

현재 이 문제의 티어는 G3이지만, 소 순서가 고정돼있다보니, 그렇게 어렵진 않다고 생각한다.

문제가 영어다보니, 조그마한 해석 실수로도 시간이 상당히 오래 걸릴 수 있다는 교훈(?)을 느꼈다.

원래 빨리 해결하고 자려 했는데, 생각보다 삽질 많이 한 문제...