백준 17420 - 깊콘이 넘쳐흘러

www.acmicpc.net/problem/17420

 

개인적으로 이 문제는 지문이 난해하다고 생각한다.

 

지문을 정리하면

 

사용 기한이 $A_i$일 남은 기프티콘을 $B_i$일 후에 쓸 계획인데

 

기프티콘을 한번 연장하면 30일 연장이 된다.

 

기프티콘을 쓸 때는 사용 기한이 제일 촉박한 기프티콘을 먼저 사용한다.

 

기한이 가장 적게 남은 기프티콘이 여러개면 아무거나 사용할 수 있으며 하루에 여러 기프티콘을 쓰거나 연장할 수 있다.

 

기프티콘을 모두 사용하는 최소 연장 횟수를 구하라.

 

 

문제를 푸는데 핵심인 부분은 입력에 써있는 설명과

 

'기프티콘을 쓸 때는 사용 기한이 제일 촉박한 기프티콘을 먼저 사용한다.

기한이 가장 적게 남은 기프티콘이 여러개면 아무거나 사용할 수 있으며 하루에 여러 기프티콘을 쓰거나 연장할 수 있다.'

 

이 부분이다. 분석해보자.

 

문제 입력 설명 따르면 i번째 기프티콘은 $B_i$ 일 후에 써야 하는데 사용 기한이 제일 촉박한 기프티콘을 먼저 사용해야 한다면 $B_i$일 후에 써야할 $i$번째 기프티콘의 사용 기한이 가장 적게 남아야 한다는 의미로 해석할 수 있다.

 

남은 기한이 동일한 기프티콘들이 있어도 i 번째 기프티콘을 소비하기만 하면 조건을 만족하면서도 답을 구할 수 있다.

 

하루에 여러 기프티콘을 연장할 수 있다는 문제를 푸는데 있어 영향을 미치지 않는다.

 

이를 통해 우리는 그저 각 기프티콘이 사용일에 사용할 수 있도록 적절히 기한 연장을 해주고 $B_i$일 후에는 $i$번째 기프티콘을 쓸 수 있도록 $i$ 번째 기프티콘의 사용 기한 <= $i + 1$ 번째 기프티콘의 사용기한이 되도록 추가 연장을 해주고 그 횟수를 구하면 답이 된다.

 

코드의 구현은 가장 먼저 사용할 날의 오름차순으로 정렬 한 후, 각 기프티콘마다 사용일이 되기 전에 만료되는 기프티콘을 연장해준다.

 

그런 다음 map<int, vector<int>>을 사용하여 각 Bi일에 쓸 기프티콘을 벡터로 묶어주고 이 벡터도 정렬해준다. 그 이유는 $i + 1$ 번째 계획일에 사용할 기프티콘들은 $i$ 번째 계획일에 사용할 기프티콘에서 기한이 가장 많이 남은 기프티콘보다 같거나 크게 기한을 가지고 있어야 조건에 위배되지 않고 기프티콘을 쓸 수 있기 때문에 i 번째 계획일에 사용할 기프티콘들의 남은 기한의 최댓값을 찾기 위해서다.

 

그러면 map의 특성상 알아서 오름차순 정렬이 되는데 comp와 pivot 반복자를 선언하여 comp는 i번째 계획, pivot은 $i + 1$ 번째 계획으로 놓고 $i + 1$ 번째 계획에 사용할 기프티콘들이 $i$ 번째에서 가장 많이 남은 기한보다 크도록 기한 연장을 해주면서 총 연장 횟수를 출력해주면 된다.

 

물론 기한 연장을 통해 벡터가 정렬되지 않은 상태가 될 수 있으므로 $i + 2$ 번째로 넘어가기 전에 정렬을 수행해야 한다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;
using ll = long long;

ll cnt;

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

    int n;
    cin >> n;

    vector<int> remain(n), will(n);

    for (int &t : remain)
        cin >> t;
    for (int &t : will)
        cin >> t;
    
    vector<pii> v(n);
    for (int i = 0; i < n; ++i)
        v[i] = {will[i], remain[i]};
    sort(v.begin(), v.end());

    for (auto &item : v)
    {
        if (item.second < item.first)
        {
            int diff = item.first - item.second;
            int tmp = diff / 30 + (diff % 30 != 0);
            cnt += tmp, item.second += 30 * tmp;
        }
    }

    map<int, vector<int>> mp;

    for (int j = 0; j < n; ++j)
    {
        if (!mp.count(v[j].first))
            mp[v[j].first] = {v[j].second};
        else
            mp[v[j].first].push_back(v[j].second);
    }

    for (auto t = mp.begin(); t != mp.end(); ++t)
        sort(t->second.begin(), t->second.end());

    auto pivot = mp.begin(), comp = mp.begin();
    ++pivot;

    while (pivot != mp.end())
    {
        ll longest = comp->second.back();
        for (int i = 0; i < pivot->second.size(); ++i)
        {
            if (pivot->second[i] < longest)
            {
                ll diff = longest - pivot->second[i];
                ll tmp = diff / 30 + (diff % 30 != 0);
                cnt += tmp, pivot->second[i] += tmp * 30;
            }
        }
        sort(pivot->second.begin(), pivot->second.end());
        ++pivot, ++comp;
    }

    cout << cnt;
}