[백준] 플래티넘5 : (17420) 깊콘이 넘쳐흘러

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

 

사용하려는 날보다 이전 날에 사용한 기프티콘의 유효 기간보다 커야 한다는 점을 유의한다.

기프티콘 사용 계획을 오름차순으로 정렬하여, 먼저 사용하는 순서대로 로직을 설계한다.

 

다음 예시를 통해 설명한다.

4
24 2 3 29		// 기프티콘 유효 기간
25 30 30 30		// 사용하려는 날
    
ans: 6

 

남은 기프티콘의 유효 기간이 짧은 순서대로 사용해야 한다

하지만, 30일에 사용하는  2, 3, 24의 경우, 아직 25일이 지나지 않았기 때문에, 사용하지 못한다.

 

그러면 사용하려는 날을 기준으로 계산해 보자.

사용하려는 날을 오름차순으로 정렬한다.

 

25일을 보자.

현재 날짜가 25일이면, 사용할 수 있는 기프티콘으로는 24가 있다.

기프티콘의 유효 기간이 지났으므로, 연장한다. (24 -> 54)

54 > 25이므로, 25일을 끝난다.

 

30일을 보자.

현재 날짜가 30일이면, 사용할 수 있는 기프티콘으로는 2, 3, 29가 있다.

N일에 사용할 수 있는 기프티콘을 오름차순 우선순위 큐로 저장하여, "남은 기프티콘의 유효 기간이 짧은 순서대로 사용" 조건을 만족한다.

 

2 < 30 이므로, 기간을 연장한다. (2 -> 32)

3 < 30 이므로, 기간을 연장한다. (3 -> 33)

29 < 30 이므로, 기간을 연장한다. (29 -> 59)

 

32 > 30이지만, 여기서 알아둬야 할 점이 있다.

현재 날짜는 30일보다 크면서, 이 전에 사용한 날인 25일에 사용한 기프티콘보다 유효 기간이 길어야 한다.

(남은 기프티콘의 유효 기간이 짧은 순서대로 사용했으므로)

 

따라서, 32 > 30이지만 32 < 54이므로, 기간을 연장한다. (62)

33 < 54이므로, 기간을 연장한다. (63)

59 > 54이므로, 기프티콘을 사용한다.

 

결론적으론 24(1), 2(2), 3(2), 29(1)로 총 6회 연장한다.

[괄호는 연장 수를 의미]

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>
#include <algorithm>
using namespace std;
#define ll long long

// 기프티콘 사용 계획 Sort
struct cmp1 { bool operator()(const pair<ll, vector<ll>>& a, const pair<ll, vector<ll>>& b) { return a.first < b.first; } };

// 해당 사용 계획 날의 사용할 수 있는 기프티콘 기한 오름차순
struct cmp2 { bool operator()(const ll& a, const ll& b) { return a > b; } };

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

	int N;
	ll Answer = 0;
	cin >> N;

	unordered_map<int, priority_queue<ll, vector<ll>, cmp2>> m;				// N일에 사용할 기프티콘(해시) { N일, 기프티콘 유효 기간 오름차순 우선순위 큐 }
	vector<pair<ll, vector<ll>>> v;											// N일에 사용할 기프티콘(배열)

	vector<pair<ll, ll>> temp;												// N일에 사용할 기프티콘(입력 양식을 맞추기 위한 임시 배열)
	for (int i = 0, j; i < N; ++i) cin >> j, temp.push_back({ j, 0 });
	for (int i = 0, j; i < N; ++i) cin >> j, temp[i].second = j;
	for (const auto& i : temp) m[i.second].push(i.first);
	temp.clear();

	for (auto i : m)
	{
		vector<ll> temp;
		while (!i.second.empty())
		{
			temp.push_back(i.second.top());
			i.second.pop();
		}
		v.push_back({ i.first, temp });
	}
	sort(v.begin(), v.end(), cmp1());

	for (ll i = 0; i < m.size(); ++i)
	{
		ll Day = v[i].first;	// 사용하려는 날
		ll Prev = v[i].first;	// 이전에 사용하려는 날에 쓴 기프티콘 유효 기간 중 가장 큰 유효 기간
		i == 0 ? 0 : Prev = m[v[i - 1].first].top();

		ll Max = -1;
		priority_queue<ll, vector<ll>, cmp2> pq = m[Day];
		while (!pq.empty())
		{
			ll Num = pq.top();
			pq.pop();

			if (Num >= Day && Num >= Prev) Max = max(Max, Num);			// 기프티콘 유효 기간이 사용하려는 날보다 크며,
			else														// 이전에 사용하려는 날에 쓴 기프티콘 유효 기간보다 커야 함
			{
				ll div = ceil((max(Day, Prev) - Num) / (double)30);		// 연장해야 하는 횟수 구하기
				Num += div <= 1 ? 30 : 30 * div;
				Answer += div <= 1 ? 1 : div;
				pq.push(Num);
			}
		}
		// 다음 사용하려는 날에서 사용할 가장 큰 유효 기간 저장
		m[Day] = pq;
		m[Day].push(Max);
	}

	cout << Answer << "\n";
}