BOJ 1781 - 컵라면

www.acmicpc.net/problem/1781

1781번: 컵라면

 

처음에 문제 풀때는 그냥 각 데드라인 마다 최대 값을 골라서 처리하면 될것이라 생각하고 문제를 잘못이해하고 있었다.

예를들면 아래 같은 코드 처럼

#include <bits/stdc++.h>
 
using namespace std;
 
int N, answer;
vector<pair<int, int>> vec; // 데드라인, 컵라면수 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    int x, y;
    for (int i = 0; i < N; ++i) {
        cin >> x >> y;
        vec.push_back({x, y});
    }
    
    sort(vec.begin(), vec.end());
    
    int dead = vec[0].first, ramen = vec[0].second;
    for (int i = 1; i < vec.size(); ++i) {
        // 데드라인이 같으면 라면 큰거 고르면되고
        // 데드라인이 다르면 새 대드라인으로 바꾸고 동시에 라면 계산
        if (dead == vec[i].first) {
            ramen = max(ramen, vec[i].second);
        } else {
            answer += ramen;
            dead = vec[i].first;
            ramen = vec[i].second;
        }
    }
    
    answer += ramen;
    
    cout << answer;
    
    return 0;
} 

 

그러나 다음과 같은 반례들에서 막혔다

N = 7
1 9
1 100
2 300
2 99
3 100
5 100
5 999

wrong : 1499
correct : 1599

 

N = 9
5 5
4 6
4 12
3 8
4 18
2 10
2 5
1 7
1 14

 

wrong : 55

correct : 59

 

위와 같은 반례들은, 데드라인별로 최대 값을 가진것을 뽑아내는게 아니라,

하루하루 경과를 시켜주면서, 데드라인 안에 있는 날짜라면, 자신의 날짜값 보다도 값이 더 큰 데드라인의 값을 선택할 수 있는 것이다.

그래서 처음 작성한 코드가 답이 되지 못했다.

그러므로, 하루씩 날짜를 진행시키면서, 최대값들을 뽑아내야되는데, 이때 최대힙을 쓰면 유용하게 뽑아낼 수 있다.

편의상 데드라인을 오름차순으로 정렬시키고, 탐색할때는 뒤에서 부터 탐색한다.

왜냐면, 현재의 날짜 보다 데드라인이 더 긴 날짜의 라면갯수가 더 많을 수도 있기 때문이다.

예를 들면, 위의 두번째 반례에서,

3일차가 되는 순간에, 3일차의 값 8을 선택하는게 아니라, 4일 데드라인의 값 18을 선택하면 최댓값으로 만들 수 있다.

 

1일차 : 14개 (1일 데드라인)

2일차 : 10개 (2일 데드라인)

3일차 : 18개 (4일 데드라인)

4일차 : 12개 (4일 데드라인)

5일차 : 5개 (5일 데드라인)

 

 

- c++

#include <bits/stdc++.h>
 
using namespace std;
 
int N, answer;
vector<pair<int, int>> vec; // 데드라인, 컵라면수 
 
int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    
    cin >> N;
    
    int x, y;
    for (int i = 0; i < N; ++i) {
        cin >> x >> y;
        vec.push_back({x, y});
        --vec[i].first; // 편의상 인덱스 맞추기 위해 하나뺌 
    }
    
    sort(vec.begin(), vec.end());
    
    priority_queue<int> pq; // 최대힙 
    int idx = N - 1;
    
    for (int day = N - 1; day >= 0; --day) {
        while(idx >= 0 && vec[idx].first == day) { // 같은 데드라인일때, 힙에 추가
            pq.push(vec[idx].second);
            idx--;
        }
        
        if (!pq.empty()) { // 최댓값만 빼냄
            answer += pq.top();
            pq.pop();
        }
    }
    
    cout << answer;
    
    return 0;
}