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

문제 이해

- 각 문제는 데드라인과 보상이 별개로 존재한다.

- 데드라인은 N 이하의 자연수이다.

- 각 문제에 대한 보상과 총 보상은 2^31보다 작은 자연수이다.

 

<조건>

- 시간 제한: 2초

- 메모리 제한: 256MB

 

<입력>

- N: 숙제의 개수 (1 ~ 200,000, 10^5)

- (데드라인, 풀면 받는 컵라면 수)

 

<출력>

- 동호가 받을 수 있는 최대 컵라면 수를 구하라.

 

 

문제 풀이

처음에 접근한 방식은 하루에 풀 수 있는 문제는 1개이므로

 

데드라인과 보상을 pair형으로 묶은 뒤,

첫 번째 인자를 데드라인으로 올림차순으로 정렬

같다면 두 번째 인자인 보상을 내림차순으로 정렬하여 진행하였다.

정렬을 통해 그리디가 구현되었다고 생각하고

슬라이딩 윈도우로 하루마다 선택해주는 방식으로 진행했는데,

4
1 50
2 30
3 60
3 70

위와 같은 반례를 통과할 수 없었다.

 

위의 반례는

1 50

3 60

3 70

세 개를 푸는게 제일 컵라면을 많이 받는 방법인데

이는 오름차순으로는 도저히 구현할 수 없었다.

 

그래서 데드라인을 내림차순으로 정렬한 뒤, 뒤에서부터 선택하는 방법으로 변경했다.

 

 

또한 슬라이딩 윈도우 방식으로 구현하는데 무언가 한계가 느껴졌기에

우선순위 큐로 구현 방법을 변경하였다.

※ 우선순위 큐는 기본이 내림차순이기에 따로 변경할 부분은 없었다.

 priority_queue<int> pq;
    for(int i = n; i > 0; i--){
        int size = v[i].size();
        for(int j = 0; j < size; j++){
            pq.push(v[i][j]);
        }
        if(!pq.empty()){
            ans += pq.top();
            pq.pop();
        }
    }

 

 

여기서 팁은, 데드라인이 같은 날짜인 것은 우선순위 큐에 한꺼번에 넣어야 하는데

while문을 통해 조건을 걸어 넣는 것도 좋지만,

입력 받을 때 벡터 배열을 사용하면 더욱 쉽게 구현할 수 있다.

v[deadline].push_back(reward);

 

 

전체 코드

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

int n, ans = 0;
vector <int> v[200005];

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

    cin>>n;
    for(int i = 0; i < n; i++){
        int deadline, reward;
        cin>>deadline>>reward;
        v[deadline].push_back(reward);
    }

    priority_queue<int> pq;
    for(int i = n; i > 0; i--){
        int size = v[i].size();
        for(int j = 0; j < size; j++){
            pq.push(v[i][j]);
        }
        if(!pq.empty()){
            ans += pq.top();
            pq.pop();
        }
    }

    cout<<ans;
    return 0;
}

앞에서부터 푸는 방식에서 반례가 발생한다면, 뒤에서부터 푸는 방식으로 고려해보는 능력을 기르자.