[백준 BOJ/C++] 1781 컵라면

1781번: 컵라면

주어진 문제 리스트에서 각 시간당 가장 많은 보상을 얻을 수 있도록 최선의 선택을 해야하는 문제다.
문제 설명이 자세하진 않은 편이라 완전히 이해는데 시간이 좀 걸렸다.
풀고 나면 간단하고 구현도 쉽지만 그리디 문제 답게 접근하는 방법이나 아이디어를 떠올리기가 만만치는 않은 문제다.

 

 

한 시간에 한 문제씩 풀 수 있는데 각 문제에는 데드라인이 있어서 해당 시간 내에 풀어야 한다.
즉 반드시 그 시간에 푸는 것이 아니라 데드라인 시간 이전 어느 시간이든 풀 수 있다.
또한 데드라인은 얼마든지 중복될 수 있어서 매 시간마다 어떤 문제를 선택하는지에 따라 총 보상 수가 달라진다.

 

 

마치 각 조합을 모두 탐색해 최적해를 찾는 문제처럼 보이기도 하지만 문제의 수 N이 200,000으로 커서 모든 경우의 수를 따지지 않고 선택할 수 있어야 시간초과에 걸리지 않는다.

 

 

---

 

 

문제의 포인트

1. 데드라인의 의미
2. 시간초과 피하기

 

 

데드라인의 의미

각 문제에는 데드라인과 보상 컵라면 수라는 속성이 존재한다.
쉽게 생각하면 데드라인을 문제를 푸는데 걸리는 시간으로 오해할 수 있는데 이렇게 되면 보상 수를 시간으로 나눠서 효율을 계산하고자 할 수 있지만 문제를 잘못 이해한 것이다.

 

 

주어지는 시간은 말 그대로 deadline으로 해당 시간 이전까지만 풀 수 있으면 언제 풀든 무관하다.
따라서 특정 시간에 풀 문제는 그 시간보다 데드라인이 더 큰 모든 문제가 후보가 된다.

 

 

문제 번호	1	2	3	4	5	6	7
데드라인	6	6	6	6	6	6	6
컵라면 수	6	7	2	1	4	5	1

 

 

예를 들어 위와 같이 모든 문제의 데드라인이 6일 경우 1~6 시간까지 7문제 중 6문제를 풀 수 있다.
데드라인이 같은 문제들 끼리만 비교하는 것이 아니라 현재 시간보다 데드라인이 큰 모든 문제가 선택의 대상이 되는 것이다.

 

 

간단히 생각해보면 각 시간마다 해당 시간보다 데드라인이 큰 문제들을 비교해서 선택하면 되겠지만 문제 수가 많아지거나 최대 데드라인이 길어진다면 상당히 많은 반복 비교를 해야한다.

 

 

시간초과 피하기

주어지는 시간이 데드라인이다보니 모든 경우를 따지려 한다면 반복 비교가 불가피 하다.
더욱이 문제의 수와 데드라인 N은 최대 200,000 으로 크기 때문에 모든 조합을 탐색하는 방식으로 최적해를 찾고자 한다면 시간초과를 피할 수 없다.

 

 

그렇다면 반대로 선택하는 방식이 아니라 일단 순서대로 쌓으면서 데드라인에 걸릴 문제를 제거하는 방식으로 접근해볼 수 있다.
즉, 각 시간마다 풀 수 있는 모든 문제들을 쌓아가면서 현재 시간보다 많은 문제가 쌓였다면 컵라면 수가 낮은 문제부터 제거해 나가는 방식이다.
아래와 같은 순서로 풀어갈 수 있겠다.

 

 

1. 문제를 리스트에 넣는다.
2. 데드라인 순서로 문제 리스트를 정렬시킨다.
3. 컵라면이 작은 문제부터 큰 문제 순서로 정렬될 수 있는 priority queue (min heap)을 준비한다.
4. 각 문제를 리스트에서 꺼내 priority queue에 넣는다.
5. 만약 현재 넣은 문제의 데드라인보다 queue의 크기가 크다면 queue에서 가장 앞의 문제를 꺼낸다.
6. queue의 크기를 queue에 넣은 문제의 데드라인과 같게 유지하면서 위 과정을 반복한다.
7. 모든 문제를 리스트에서 다 꺼냈다면 queue에 남은 문제들의 컵라면 수를 합한다.

 

 

과정이 복잡해 보일 수 있지만 정리해보면 간단한 과정이다.
핵심은 가장 컵라면 수가 적은 문제를 꺼낼 수 있는 우선순위 큐에 문제를 넣어가되, 해당 문제의 데드라인만큼의 크기로 큐를 유지시키는 것이다.

 

 

한시간에 한문제씩 풀 수 있으므로 큐의 크기는 각 시간에 풀 문제를 쌓는 것이되며 큐의 크기가 마지막에 넣은 문제의 데드라인보다 크다면 문제를 풀 수 있는 시간보다 문제 수가 많아졌다는 의미다.

 

 

컵라면 수를 기준으로 우선순위 큐를 만들었기 때문에 가장 앞에서 문제를 뺀다면 현재 시간까지 풀 수 있는 문제 중 가장 보상이 적은 문제를 제거하는 것이 된다.

 

 

문제 번호	1	2	5	6	3	4	7
데드라인	1	1	2	2	3	3	6
컵라면 수	6	7	4	5	2	1	1

 

위와 같이 문제 리스트를 데드라인 순서로 정렬시켰다고 하자.

 

 

 

리스트에서 순서대로 우선순위 큐에 집어넣는다.
가장 먼저 1번 문제가 들어가고 그 다음으로 2번 문제가 들어간다.
2번 문제는 데드라인이 1인데 큐의 크기가 2가 되기 때문에 큐에서 가장 위에 있는 1번 문제를 제거한다.

 

 

그 다음으로 5번 문제를 큐에 넣는다.

5번 문제의 데드라인은 2이고 큐의 크기가 2이므로 문제를 제거할 필요는 없다.

 

 

 

이번에는 6번 문제를 넣는다.
6번 문제는 데드라인이 2인데 큐가 3으로 늘었으므로 컵라면 수가 4인 5번 문제를 제거한다.

 

 

그 다음으로 3번 문제를 큐에 넣는다.
데드라인이 3이므로 문제를 제거하지 않는다.

 

 

 

이어서 4번 문제를 넣는다.
데드라인이 3인데 큐에 4개가 쌓였으니 컵라면 수가 가장 적은 4번 문제를 제거한다.

 

 

마지막으로 7번 문제를 넣으면 데드라인이 6이고 큐의 사이즈가 4라서 제거할 필요 없이 끝낸다.
이제 큐에 쌓인 문제의 컵라면 수를 모두 합하면 답이된다.

 

 

---

 

전체 Code

 

#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

vector<pair<int, int>> V;
priority_queue<int, vector<int>, greater<int>> pq;

int N;

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

	int i, d, c;
	int max_sum = 0;

	cin >> N;

	for (i = 0; i < N; i++) {
		cin >> d >> c;
		V.push_back(make_pair(d, c));

	}

	sort(V.begin(), V.end());

	for (i = 0; i < V.size(); i++) {
		pq.push(V[i].second);

		if (pq.size() > V[i].first)
			pq.pop();
	}

	while (!pq.empty()) {
		max_sum += pq.top();
		pq.pop();
	}

	cout << max_sum << "\n";
    
	return 0;
}