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

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

 

 

이 문제는 컵라면 종류가 주어지고 각 컵라면마다 데드라인, 개수가 주어진다. 이때 최대로 얻을 수 있는 컵라면 개수를 출력하는 문제이다.

 

컵라면을 얻기 위해 문제를 풀어야 하는데 한 문제를 풀때 1시간이 걸린다.

 

이때 숙제의 개수가 최대 20만이다.

 

처음 생각한 방법은 20만 배열을 만들어 컵라면 개수를 내림차순으로 정렬하여 

 

일자 인덱스에 기록되지 않은 경우 더해주며 만약 이미 기록된 경우 현재 일자부터 1씩 감소시키면서 빈 날짜를 찾아서 할당 해 줄 생각을 하였다.

 

하지만 이는 시간복잡도가 최대 O(N^2)으로 시간초과가 나는 코드이므로 다른 방법을 생각했어야 했다.

 

결국 데드라인이 있을때 그 데드라인에 맞춰 최대로 먹어야 한다. 필자는 최소 힙을 사용하여 날짜 순으로 오름차순 정렬하였다.

 

최소힙이 의미하는 것은 지정한 날짜를 확인했을때 최대로 먹을 수 있는 컵라면 개수를 담는 컨테이너이다.

그렇게 되면 

(1, 6)

(1, 7)

(2, 4)

(2, 5)

(3, 1)

(3, 2)

(6, 1)
로 되며

순차적으로 힙에 컵라면 개수를 넣어준다. 이때 우선순위 큐의 크기가 데드라인보다 커지는 경우 이는 한정된 데드라인에 해당 힙에 크기만큼 컵라면 개수를 먹을 수 없기 때문에 가장 작은 컵라면 개수(top)부분을 빼주었다.

 

 

정답코드

#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define endl "\n"
#define MAX 1e9

struct coordinate {
    int x;
    int y;
    int r;
};

struct halloween {
    int cnt;
    int score;
};

// int dx[] = {-1, 1, 0, 0, 1, -1, -1, 1};
// int dy[] = {0, 0, -1, 1, -1, 1, -1, 1};
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int N;
vector<pii> v;

void solve() {
    sort(v.begin(), v.end());

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

    for(auto it : v) {
        int day = it.first;
        int cost = it.second;
        pq.push(it.second);

        if(day < pq.size()) {
            pq.pop();
        }
    }

    ll answer = 0;
    while(!pq.empty()) {
        answer += pq.top();
        pq.pop();
    }

    cout << answer;
}

void input() {
    cin >> N;

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

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    input();
    solve();
}