백준 1781 c++ "컵라면" -PlusUltraCode-

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

[필자 사고]

재미난 문제다. well known 문제.. 

먼저 해당 값들을 데드라인 기준으로 sort 정렬한다.

그뒤 우선순위 큐를 이용하여 ramen 의 값을 저장하고 .

우선순위 큐의 size를 이용하여 데드라인과 비교한다.

 

여기서 재미난 점이 ramen의 값은 우선순위 큐 덕분에 큰값은 끝으로 작은값은 알아서 앞으로 온다.

결국 우선순위 큐에는 가장 최적의 큰 값들만 남게 된다.

 

아래는 자세한 코드 해설이다.

[코드 해설]

이 코드는 백준 1781번 컵라면 문제를 구조체(Node)와 우선순위 큐(min-heap)로 구현한 풀이이다.

---

코드 설명

1. 입력 및 데이터 저장

int N;
vector<pair<int,int>> arr;
cin >> N;
for (int i = 0; i < N; i++) {
	int a, b;
	cin >> a >> b;
	arr.push_back({ a,b });
}

• N: 문제 개수
• arr: (데드라인, 컵라면) 쌍 저장

2. 정렬

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

• 데드라인 기준 오름차순 정렬
• 같은 데드라인일 경우 입력 순서에 따라 처리

3. 최소 힙 구성

typedef struct Node {
	int ramen;
} Node;

struct cmp {
	bool operator()(const Node& a, const Node& b) const {
		return a.ramen > b.ramen;
	}
};
priority_queue<Node, vector<Node>, cmp> pq;

• Node 구조체는 ramen 값을 가짐
• cmp는 ramen이 작은 값이 우선순위가 높도록 설정 (즉, min-heap)

4. 문제 선택 로직

for (int i = 0; i < arr.size(); i++) {
	int ramen = arr[i].second;
	int deadLine = arr[i].first;

	pq.push({ ramen });

	while (1) {
		if (pq.size() > deadLine) {
			pq.pop();
		}
		else {
			break;
		}
	}
}

• 문제를 데드라인 순으로 순회하면서 최소 힙에 추가
• 현재까지 푼 문제 수(pq.size())가 deadLine을 초과하면,
  가장 적은 컵라면 문제를 버림 (pq.pop())

이 과정을 통해 항상 “해당 시점에서 가능한 최대 컵라면 조합”을 유지함.

5. 총합 계산

int sum = 0;
while (!pq.empty()) {
	sum += pq.top().ramen;
	pq.pop();
}
cout << sum;

• 힙에 남은 문제들의 컵라면 수를 모두 더함
• 결과가 동호가 받을 수 있는 최대 컵라면 수

---

핵심 요약

• 데드라인 기준 정렬
• 최소 힙으로 컵라면 수 관리
• 데드라인 초과 시 가장 작은 컵라면 제거
• 최종 힙 합계가 최대 보상

시간 복잡도: O(N log N)
공간 복잡도: O(N)

이 방식은 “데드라인이 긴 문제라도 컵라면이 많으면 더 이득인 경우”를 자동으로 반영한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N;


typedef struct Node {
	int ramen;
}Node;

struct cmp {
	bool operator()(const Node& a, const Node& b) const {
		return a.ramen > b.ramen; // ramen 작은 게 top에 오도록
	}
};
vector<pair<int,int>> arr;
int main(void) {
	cin >> N;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		arr.push_back({ a,b });
	}
	priority_queue<Node, vector<Node>, cmp> pq;

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

	for (int i = 0; i < arr.size(); i++) {
		int ramen = arr[i].second;
		int deadLine = arr[i].first;

		pq.push({ ramen });

		while (1) {
			if (pq.size() > deadLine) {
				pq.pop();
			}
			else {
				break;
			}
		}
	}
	int sum = 0;
	while (!pq.empty()) {
		sum += pq.top().ramen;
		pq.pop();
	}

	cout << sum;

}