[백준/BOJ] 백준 1781번 : 컵라면

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

1781번: 컵라면

데드라인이 가장 긴 수 중 가장 큰 컵라면 수는 무조건 고르고, 그다음에는 문제를 선택하는 시간을 그 데드라인 시간-1부터 -1 씩 해간다 즉,  가장 긴 데드라인 시간에서 1시간까지 해당 시간에 풀 수 있는 문제 중 가장 많은 컵라면의 개수를 골라 가면 최대 컵라면의 개수와 같다

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <set>
using namespace std;

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

	int n;
	int deadline, ramen;
	vector<pair<int, int>> input;
	int sum = 0;
	int choice_time;
	multiset <int, greater<int>> choice_temp_ramen; //내림차순 정렬

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> deadline >> ramen;
		input.push_back(make_pair(deadline, ramen));
	}

	//입력받은것을 내름차순으로 정렬한다
	sort(input.begin(), input.end());
	reverse(input.begin(), input.end());

	//데드라인이 가장 긴 수 중 가장 큰 컵라면 수는 무조건 고른다
	sum += input[0].second;

	//다음에는 데드라인 시간 - 1(input[0].first - 1)시간에 풀 문제를 고른다
	choice_time = input[0].first - 1;

	for (int i = 1; i < n; i++)
	{
		//현재 선택시간보다 데드라인이 더 긴것은 고를 수 있으므로
		//일단 현재 선택시간에 고를 후보에 넣는다
		if (input[i].first > choice_time)
		{
			choice_temp_ramen.insert(input[i].second);
		}

		//현재 선택 시간과 데드라인 시간이 같다면 이 데드라인 시간에 처음 만난 문제가 같은 데드라인중에서 컵라면 수가 제일 크므로
		//이전에 계산한 현재 선택 시간에 고를 후보들 중 가장 큰것과 이때의 컵라면 개수 중에 큰 것을 고른다
		else if (input[i].first == choice_time)
		{
			//고를 후보 목록이 비어있지 않다면
			if (!choice_temp_ramen.empty())
			{
				//이전에 계산한 현재 선택 시간에 고를 후보들중 가장 큰 것이 지금 컵라면 개수보다 크거나 같다면 그것을 고른다
				if (*choice_temp_ramen.begin() >= input[i].second)
				{
					sum += *choice_temp_ramen.begin();
					choice_temp_ramen.erase(choice_temp_ramen.begin()); //고른것은 고를 목록에서 지운다

					//input[i]은 비록 지금 시간에서는 선택되지 않았지만 나중에 고를 수 있으므로 고를 후보에 넣는다
					choice_temp_ramen.insert(input[i].second);
				}

				//이때의 컵라면 수가 어떤 후보들 보다 더 크다면 이것을 고른다
				else
					sum += input[i].second;
			}

			//후보 목록이 비어있다면 이것을 고른다
			else
				sum += input[i].second;

			choice_time--; //choice_time시간에 고를건 골랐으므로 다음엔 choice_time-1시간에 고를것을 찾는다
		}

		//이 때의 문제는 choice_time 시간에 풀 수 없으므로
		//이전에 계산한 고를 후보가 있을 때는 그중 가장 큰것을 고른다
		else if (input[i].first < choice_time)
		{
			//이전에 계산한 고를 후보가 있을 때
			if (!choice_temp_ramen.empty())
			{
				sum += *choice_temp_ramen.begin();
				choice_temp_ramen.erase(choice_temp_ramen.begin()); //고른것은 목록에서 지운다
			}
			choice_time--;//choice_time시간에 고를건 골랐으므로 다음엔 choice_time-1시간에 고를것을 찾는다
			i--; //이때의 문제를 푸는 시간까지 오지 않았으므로 이 문제는 다음에도 고려하기 위해 i--한다
		}
	}

	//현재 고르는 시간(choice_time)이 0에 도달하지 않았으면
	//choice_time번 더 고를 수 있으므로 고를 후보 목록에서 큰 순서 대로 고른다
	for (int i = choice_time; i > 0; i--)
	{
		if (!choice_temp_ramen.empty())
		{
			sum += *choice_temp_ramen.begin();
			choice_temp_ramen.erase(choice_temp_ramen.begin());
		}
	}

	cout << sum;

	return 0;
}