[Baekjoon(백준)][1781번] 컵라면(C++)

이 문제는 N개의 문제에 대해 각 문제를 풀었을 때 받을 수 있는 컵라면 수와 해당 문제를 풀어야 하는 마감시간(데드라인)이 주어졌을 때, 동호가 받을 수 있는 최대 컵라면 수를 구하는 문제입니다. 각 문제는 데드라인 안에 풀어야 하고, 문제를 풀 때 걸리는 시간은 1시간입니다.

문제링크:

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

 

문제 분석

문제의 조건:

• 각 문제는 단위 시간 1이 걸리며, 각 문제마다 주어진 데드라인 내에 풀어야 합니다.
• 각 문제를 풀면 받을 수 있는 컵라면 수가 주어집니다.
• N개의 문제 중 데드라인 내에서 최대한 많은 문제를 풀어 최대 컵라면을 얻어야 합니다.

접근 전략:

• 각 문제를 데드라인이 짧은 순서대로 풀면서, 컵라면 수를 최대화해야 합니다.
• 만약 데드라인보다 많은 문제를 풀고 있다면, 그 중에서 이익(컵라면 수)이 가장 작은 문제를 제외하는 방식으로 접근할 수 있습니다. 이를 효율적으로 처리하기 위해 우선순위 큐(Min Heap, 최소 힙)를 사용합니다.

해결 방법

1. 데드라인 기준으로 정렬: 먼저, 모든 문제를 데드라인 기준으로 오름차순 정렬합니다. 이렇게 하면 데드라인이 짧은 문제부터 처리할 수 있어, 각 문제의 데드라인을 최대한 지킬 수 있습니다.
2. 우선순위 큐 사용: 각 문제를 처리할 때마다, 우선순위 큐에 컵라면 수를 추가합니다. 큐의 크기가 해당 문제의 데드라인을 초과할 경우, 가장 작은 컵라면 수를 가진 문제를 제거합니다. 이렇게 하면 더 적은 컵라면 수를 얻는 문제를 제외하고, 최대 이익을 얻는 문제들만 선택할 수 있습니다.
3. 최종 이익 계산: 모든 문제를 처리한 후, 우선순위 큐에 남아있는 컵라면 수들을 모두 더하면 최대 이익을 구할 수 있습니다.

코드 구현

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

int n;
vector<pair<int, int>> tasks; // {데드라인, 컵라면 수}
priority_queue<int, vector<int>, greater<int>> pq; // 최소 힙 (최소 컵라면 수 관리)

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

    cin >> n;

    // 입력 받기
    for (int i = 0; i < n; i++) {
        int deadline, ramen;
        cin >> deadline >> ramen;
        tasks.push_back({deadline, ramen});
    }

    // 데드라인 기준으로 오름차순 정렬
    sort(tasks.begin(), tasks.end());

    // 각 문제를 처리
    for (auto task : tasks) {
        pq.push(task.second); // 현재 문제의 컵라면 수를 힙에 넣기

        // 현재 처리할 수 있는 문제 수보다 많으면 최소 컵라면 수 제거
        if (pq.size() > task.first) {
            pq.pop();
        }
    }

    // 남은 문제들의 컵라면 수 합산
    int totalRamen = 0;
    while (!pq.empty()) {
        totalRamen += pq.top();
        pq.pop();
    }

    cout << totalRamen << endl; // 최대 컵라면 수 출력

    return 0;
}

코드 설명

1. 입력 처리:
   • n개의 문제 정보를 입력받아 tasks 벡터에 저장합니다. 각 문제는 {데드라인, 컵라면 수} 쌍으로 저장됩니다.
2. 데드라인 기준 정렬:
   • sort(tasks.begin(), tasks.end())를 통해 데드라인 기준으로 오름차순 정렬합니다. 이를 통해 데드라인이 짧은 문제부터 처리할 수 있게 됩니다.
3. 우선순위 큐 사용:
   • 문제를 하나씩 처리하며, 해당 문제의 컵라면 수를 우선순위 큐에 삽입합니다.
   • 만약 큐의 크기가 해당 문제의 데드라인을 넘으면, 가장 작은 컵라면 수를 가진 문제를 제거합니다. 이는 데드라인 내에서 더 많은 컵라면을 얻을 수 있는 문제를 선택하기 위한 전략입니다.
4. 최대 컵라면 수 계산:
   • 큐에 남은 컵라면 수들을 모두 더하여 최대 컵라면 수를 출력합니다.

시간 복잡도 분석

1. 정렬: O(n log n)
   문제의 데드라인을 기준으로 정렬하는 데 n log n 시간이 걸립니다.
2. 우선순위 큐 관리: O(n log k)
   각 문제에 대해 우선순위 큐에서 삽입과 삭제를 하므로, 각 연산은 log k 시간(여기서 k는 우선순위 큐의 크기)이 걸립니다.

따라서 전체 시간 복잡도는 O(n log n)입니다. N의 최대값이 200,000이므로, 이 시간 복잡도는 제한 시간 2초 내에 충분히 처리 가능합니다.

결론

이 문제는 데드라인과 컵라면 수라는 두 가지 요소를 기반으로 그리디 알고리즘과 우선순위 큐를 결합하여 최적의 해결책을 찾는 문제입니다. 데드라인이 짧은 순서대로 문제를 풀면서, 적은 이익을 주는 문제를 제외해 나가는 방식으로 최대 이익을 얻는 전략이 핵심입니다.