알고리즘/백준

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

KANTAM 2024. 3. 6. 21:37

문제

 

1781번: 컵라면

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라

www.acmicpc.net

풀이

그리디, 우선순위 큐

 

 

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

문제 2109번: 순회강연 한 저명한 학자에게 n(0 ≤ n ≤ 10,000)개의 대학에서 강연 요청을 해 왔다. 각 대학에서는 d(1 ≤ d ≤ 10,000)일 안에 와서 강연을 해 주면 p(1 ≤ p ≤ 10,000)만큼의 강연료를 지불

kantatatam.tistory.com

위의 문제와 같지만 이 문제가 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;
}