[G4] 백준 24041번 성싶당 밀키트 C++ 이분 탐색, 매개 변수 탐색, 그리디 알고리즘

리뷰

 

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

숫자 범위를 잘 설정해야 하는 이분 탐색 문제

 

 

전역 변수

• N : 배열의 최대 크기를 정의할 상수 변수
• n : 밀키트 재료의 개수를 저장할 변수
• g : 먹을 수 있는 최대 세균 수를 저장할 변수
• k : 제외할 수 있는 재료의 개수를 저장할 변수
• pq : 제외할 수 있는 재료의 현재 세균수를 담을 우선순위 큐
• Info : 밀키트 재료 정보를 정의할 구조체
• ing : 밀키트 재료 정보를 저장할 Info타입 배열

 

함수

없음

 

 

문제풀이

1. n, g, k값을 입력 받고, n개의 밀키트 재료를 입력 받아 ing배열을 초기화한다.
2. 변수 l을 0, r을 20억, ans를 -1로 초기화한다.
3. l이 r이하일 경우를 조건으로 하는 while루프를 수행한다.
4. 변수 mid를 l+r을 2로 나눈 몫으로 저장한다.
5. n개의 밀키트 재료의 현재가 mid일일 때의 세균수를 구해 제거할 수 있는 재료면 A, 아니면 B에 추가한다.
6. 변수 sum과 remove를 0으로 초기화한다.
7. 현재 일자의 세균의 합을 sum에 모두 더해준다.
8. 제거할 수 있는 재료의 경우 최대 k개 까지 pq에 추가한다.
9. pq에 있는 세균의 합을 sum에서 모두 제거한다.
10. sum이 g이하일 경우 ans에 mid를 저장하고 l을 mid+1로 변경한다.
11. sum이 g초과일 경우 r을 mid-1로 변경한다.
12. while이 종료된 후 ans에 저장된 값을 출력한다.

 

트러블 슈팅

1. r의 범위를 g의 최대값인 10억으로 잡았다가 WA를 받았다.
2. r의 범위를 20억으로 변경 했으나 mid값이 오버플로우가 발생하여 시간 초과를 받았다.
3. l, r, mid를 ll타입으로 설정하여 AC를 받았다.

 

참고 사항

1. 먹을 수 있는 최대 세균 수가 10억이고, 밀키트의 유통기한이 10억이라면 최대 20억일까지 먹을 수 있다.
2. 따라서 r범위를 최대 세균 수에 맞추는 것이 아닌 20억으로 맞춰주어야 정답을 도출할 수 있다.
3. pq는 최소힙으로 구현하여 세균 수가 많은 순서로 최대 k개 까지 담아주고, 마지막에 모두 제거해준다.

 

정답 코드

#include<iostream>
#include<queue>
using namespace std;
using ll = long long;

const int N = 2e5;
int n, g, k;
priority_queue<ll, vector<ll>, greater<ll>> pq;
struct Info {
	int S, L;
	bool O;
};
Info ing[N];

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

	cin >> n >> g >> k;
	for (int i = 0; i < n; ++i) {
		int S, L;
		bool O;
		cin >> S >> L >> O;
		ing[i] = { S, L, O };
	}

	ll l = 0, r = 2e9, ans = -1;
	while (l <= r) {
		ll mid = (l + r) / 2;
		ll sum = 0;
		int remove = 0;

		for (int i = 0; i < n; ++i) {
			const Info& info = ing[i];
			ll val = 1ll * info.S * max(1ll, mid - info.L);
			sum += val;

			if (info.O) {
				pq.push(val);
				if (pq.size() > k) pq.pop();
			}
		}

		while (!pq.empty()) {
			ll val = pq.top(); pq.pop();
			sum -= val;
		}

		//cout << sum << "\n";
		if (sum <= g) {
			ans = mid;
			l = mid + 1;
		}
		else r = mid - 1;
	}
	cout << ans;
}