[백준][C++] 1781: 컵라면

문제

1781번: 컵라면

풀이

그리디, 우선순위 큐

 

[백준][C++] 2109: 순회강연

위의 문제와 같지만 이 문제가 N이 더 크기때문에, 같은 풀이로는 시간 초과가 발생하였다. 

 

각 날짜 별로 풀 수 있는 문제 중에서 가장 value가 높은 문제를 풀어야 한다. 여기서 각 날짜 별로 풀 수 있는 문제를 구해야 한다. i일에 풀 수 있는 문제는 (i <= 데드라인)인 문제이다. 그러므로 N일부터 탐색을 실시해야 하며, 1일까지 각 날짜에 가장 value가 높은 문제를 배치해야 한다. 

 

i일에 풀 수 있는 문제 목록은 탐색과 동시에 변화된다. 이 목록 중에서 가장 value가 높은 문제를 빠르게 찾아야 하므로 우선순위 큐를 사용한다. i일에 풀 수 있는 문제를 모두 우선순위 큐에 넣으면서 탐색을 진행한다면, 우선순위 큐의 top에는 현재 풀 수 있는 문제 중에서 가장 높은 value가 위치하게 된다. 

int answer = 0;
for (int i = N; i > 0; --i)
{
    // pq에는 데드라인이 i이상인 문제만 들어가게 된다. 
    // 그러므로 pq의 top이 i번 날짜에 풀 수 있는 문제 중에서 value가 가장 높은 문제가 된다.
    for (int value : values[i])
    {
        pq.push(value);
    }

    if (!pq.empty())
    {
        answer += pq.top();
        pq.pop();
    }
}

이를 1일 까지 실시한다. 

코드

#include <iostream>
#include <queue>

using namespace std;

priority_queue<int> pq;
vector<int> values[200'001];

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

    int N;
    cin >> N;

    for (int i = 0; i < N; ++i)
    {
        int deadline, value;
        cin >> deadline >> value;

        // deadline까지 풀 수 있는 문제
        values[deadline].push_back(value);
    }

    // 첫날에 데드라인이 많이 남은 문제를 풀면 이후 풀 수 있는 문제가 없으므로 N번 날짜에 풀 문제부터 선택한다. 
    // i번 날짜에 풀 수 있는 문제는 (i <= 데드라인)인 문제이다. 
    int answer = 0;
    for (int i = N; i > 0; --i)
    {
        // pq에는 데드라인이 i이상인 문제만 들어가게 된다. 
        // 그러므로 pq의 top이 i번 날짜에 풀 수 있는 문제 중에서 value가 가장 높은 문제가 된다.
        for (int value : values[i])
        {
            pq.push(value);
        }

        if (!pq.empty())
        {
            answer += pq.top();
            pq.pop();
        }
    }

    cout << answer;

    return 0;
}