[백준] 24041번 성싶당 밀키트 - C/C++

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

24041번: 성싶당 밀키트

문제

인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 <성싶당>은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다! 이제 성싶당의 맛을 집에서도 즐길 수 있다!

이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고 포장을 뜯은 순간 한별이는 재료마다 유통기한이 다르다는 것을 발견했다. 밀키트의 유통기한은 모든 재료의 유통기한 중 가장 이른 것으로 결정되기 때문에 아직 유통기한이 지나지 않은 재료들이 남아 있었다.

밀키트에는 N 개의 재료가 들어 있다. i번째 재료의 유통기한은 밀키트를 구매한 후 Li일까지이고, 부패 속도는 Si이다. 이 때 구매 후 x 일에 i번째 재료에 있는 세균수는

 Si×max(1,x−Li)

마리이다. 단, x는 정수이다.

모든 재료의 세균수의 합이 G 마리 이하일 경우 안심하고 먹을 수 있다. 밀키트를 너무 먹어보고 싶은 한별이는 중요하지 않은 재료를 최대 K 개까지 빼서 세균수가 G 마리 이하가 된다면 그냥 먹기로 했다.

한별이는 밀키트를 산 날부터 며칠 후까지 먹을 수 있을까?

입력

첫 번째 줄에 N,G,K, 가 공백으로 구분되어 주어진다.

두 번째 줄부터 N 개의 줄 중 i번째 줄에는 i 번째 재료에 대한 정보인 부패 속도 Si, 유통기한 Li와 중요한 재료인지를 나타내는 수 Oi가 주어진다. Oi는 0 또는 1이며, Oi=1은 재료가 중요하지 않아서 뺄 수 있다는 의미이다.

출력

중요하지 않은 재료를 최대 K 개까지 뺐을 때, 밀키트를 구매 후 며칠 후까지 먹을 수 있는지 출력한다.

---

매일 N개의 재료의 세균 수를 계산하며 날짜를 구할 수도 있지만, 그렇게 되면 G의 크기가 10^9까지 갈 수 있기 때문에 매일 세균의 수를 계산하며 날짜를 늘려가는 식으로 풀었더니 시간 초과가 났다.

분할 정복을 통한 매개변수 탐색 (Parametric Search)을 하여 최대의 날짜에 다가가는 방법을 활용했다. s 는 무조건 되는 날짜 e는 무조건 안 되는 날짜이기 때문에 구간이 s+1 = e 가 되었을 때 e를 확인하여 e가 된다면 e 가 답이고 안된다면 s 가 답이 된다. 세균을 구할 때 s와 e의 중간 값 x를 활용하는데 이때 세균의 수를 정렬하여 가장 세균이 많은 재료들 중 제외할 수 있는 재료 K 개는 sum에 포함하지 않고 세균의 수를 센다. 만약 그 값이 G보다 크다면 세균이 더 많다는 뜻이다. 더 작은 일수를 선정해야 하므로 e를 x로 선택한다. 그 값이 G 보다 작다면 세균이 더 적다는 뜻이므로 일수를 늘려도 된다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
long long N, G, K;
long long s=1000000001,e=2000000001,x;
long long info[200001][3] = { 0 }; // S L O

void solve() {
	vector<pair<long long,int>> arr;
	while (1) {
		long long sum = 0;
		arr.clear();
		if (s + 1 >= e) {
			x = e;
		}
		else x = (s + e) / 2 ;

		for (int i = 0; i < N; i++) {
			arr.push_back(make_pair(info[i][0] * max((long long)1, x - info[i][1]),info[i][2]));
		}
		sort(arr.begin(), arr.end());
		int k = K;
		for (int i = arr.size() -1 ; i >= 0; i--) {			
			if (k && arr[i].second) {
				k--;
			}
			else sum += arr[i].first;
		}
		if (s + 1 >= e) {
			if (sum > G)
				cout << s;
			else
				cout << e;
			break;
		}
		else {
			if (sum > G)
				e = x;
			else
				s = x;
		}

	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> N >> G >> K;
	for (int i = 0; i < N; i++) {
		cin >> info[i][0] >> info[i][1] >> info[i][2];
		if (s > info[i][1])
			s = info[i][1];
	}
	solve();

	return 0;
}

---

맨 먼저 아래와 같은 코드를 짰는데 시간초과가 났다. 이 알고리즘 은 O(N * G)의 값이 되는데 G 가 굉장히 커 G가 시간 복잡도에 들어가면 안 될 것 같았다. 그래서 G를 logG로 풀어야 되면 분할 정복을 써야 되나? 여기서 날짜를 다루는 것인데 분할 정복은 힘들겠다고 생각했는데 분류를 보니 이분 탐색, 매개변수 탐색이라고 나와있었다. 저번에도 분류에서 매개변수 탐색을 본 것 같아 찾아보니 최댓값을 처음 e 값으로 잡고 이분 탐색을 하는 것이었다. 이분 탐색에서 크게 벗어나는 개념은 아니었지만 날짜의 개념을 2 * 10^9 승을 최댓값으로 하는 구간을 이분 탐색할 것이라고는 생각을 하지 못했다. 그리고 질문들을 보니깐 최댓값을 2* 10^9승을 생각하지 못하고 10^9승으로 생각하여 많이들 틀렸다고 한다. 세균수가 G의 최댓값이 10^9이고 L의 최댓값이 10^9이므로 2*10^9 승인 것을 이해는 했지만 막상 풀다가 틀렸으면 범위보다는 다른 코드를 위주로 봤을 것 같다. 오늘도 또 다른 유형의 문제를 익힌 것 같다!