[백준] 24041 성싶당 밀키트 (C++)

24041번: 성싶당 밀키트

문제

인스타 빵타쿠들의 꾸준한 사랑을 받는 베이커리 <성싶당>은 수현이가 그동안 쌓아온 노하우를 바탕으로 밀키트 사업에도 진출했다! 이제 성싶당의 맛을 집에서도 즐길 수 있다!
 
이 소식을 놓칠 리 없는 빵타쿠 한별이는 바로 성싶당에 달려가 밀키트를 사 왔다. 그러나 문제를 푸느라 바쁜 한별이는 깜빡 잊고 유통기한 안에 밀키트를 먹지 못했다. 눈물을 머금고 밀키트를 버리려고 포장을 뜯은 순간 한별이는 재료마다 유통기한이 다르다는 것을 발견했다. 밀키트의 유통기한은 모든 재료의 유통기한 중 가장 이른 것으로 결정되기 때문에 아직 유통기한이 지나지 않은 재료들이 남아 있었다.

밀키트에는 N 개의 재료가 들어 있다. i 번째 재료의 유통기한은 밀키트를 구매한 후 Li 일까지이고, 부패 속도는 Si 이다. 이 때 구매 후 x 일에 i 번째 재료에 있는 세균수는 Si x max(1, x-Li) 마리이다. 단, x 는 정수이다.
 
모든 재료의 세균수의 합이 G 마리 이하일 경우 안심하고 먹을 수 있다. 밀키트를 너무 먹어보고 싶은 한별이는 중요하지 않은 재료를 최대 K 개까지 빼서 세균수가 G 마리 이하가 된다면 그냥 먹기로 했다.
 
한별이는 밀키트를 산 날부터 며칠 후까지 먹을 수 있을까?
 

입력

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

 

출력

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

 

제한

1 ≤ n ≤ 200,000
1 ≤ g, Si, Li ≤ 10^9
0 ≤ k < n
 

 

---

접근 방식

문제 이해

밀키트에는 총 N개의 재료가 있다.
그 중 i 번째 재료에 <부패 속도(Si), 유통기한(Li), 중요 재료 여부(Oi)>의 3가지 조건이 주어진다.
1. 부패 속도: Si
2. 유통 기한: 구매일로부터 Li일
3. 중요 재료 여부: Oi = 1 이면 뺄 수 있는 재료 (= 중요하지 않은 재료)
 
구매 후 x일이 지났을 때, i 번 재료의 세균 수는 Si x max(1, x-Li)이다.
모든 재료의 세균 수가 G보다 작거나 같으면 먹는다.
 
단, 중요하지 않은 재료를 최대 K개까지 제외하여 위 조건을 충족해도 먹는다.
 
구매 후 n일 후에 먹는다고 할 때, n의 최댓값을 구하라.
 

접근

날짜와 제외할 재료를 고려해야 한다.
 
날이 지남에 따라, 제외할 재료의 우선순위는 달라질 수 있다. (재료마다 유통기한과 부패 속도가 다르기 때문)
두 가지 조건을 모두 고려하여, 최대 K개의 제외할 재료를 구하는 방법은 다음과 같다.
 
1. 모든 세균의 합을 구한다.
    -> 이 과정에서 Oi = 1 인 재료의 세균 수는 새로운 배열에 저장한다.
2. Oi = 1 인 재료의 세균 수가 저장된 배열을 내림차순으로 정렬한다.
3. 최대 K개 재료의 세균 수를 제외한다.
    -> 제외할 수 있는 재료의 수가 K보다 작으면, 가능한 모든 재료를 제외한다.
 

알고리즘

1. N개의 재료에 대하여, 모든 입력값을 배열에 저장한다.
2. 이분탐색
     a. 경과한 날짜에 대하여 모든 재료의 세균의 합을 구한다.
          - 이 과정에서 Oi==1인 재료의 세균 수는 한 vector에 저장해둔다.
     b. vector를 내림차순 정렬한다. (우선순위 = 세균의 수)
     c. 최대 K개 재료의 세균 수를 제외한다.
          - 제외 가능한 재료의 수가 K보다 작을 수 있으므로, min(k, vt.size())를 최대 범위로 한다.
 

시간 복잡도

H = hi의 초기값 = 2*10^9 + 1

 

이분 탐색 - O(logH)
 - 세균 수 구하기 - O(N)
 - 정렬 - O(NlogN)
 - 제외한 재료 세균 빼기 - O(N)
 
O(logH) * (2O(N) + O(NlogN)) → O(NlogN*logH)
 

제출

40% 틀렸습니다 → 맞았습니다!!
1. 40% -> hi 범위 재설정; 입력받은 Li 중 최댓값이 아니다!! 그 이상이 될 수 있다.
 

Code

코드를 보기 전에 스스로 구현해 보는 것을 권장합니다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;

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

    int n, k;
    ll g;
    ll lo=0, hi=2000000001;
    ll arr[200001][3] = { 0 };

    cin >> n >> g >> k;

    for (int i = 0; i < n; i++) cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

    ll ans=0;
    while (lo <= hi) {
        ll mid = (lo + hi) / 2;

        vector<ll> vt;
        ll germ = 0;
        for (int i = 0; i < n; i++){
            ll temp = arr[i][0] * max(1LL, mid - arr[i][1]);
            germ += temp;
            if(arr[i][2] == 1) vt.push_back(temp);
        }
        sort(vt.begin(), vt.end(), greater<ll>());

        for(int i = 0; i < min(k, int(vt.size())); i++) germ -= vt[i];

        if(germ <= g) {
            ans = max(ans, mid);
            lo = mid + 1;
        }
        else hi = mid - 1;
    }
    
    cout << ans;
}