[Algorithm]Baekjoon 2109번 : 순회강연

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

2109번: 순회강연

 
bool cmp(const Node& a, const Node& b)
{
    return a.date > b.date;
}
 
vector<Node> nodes;
vector<int> dates;
priority_queue<int, vector<int>, less<int>> pq;
int n, a, b;
unordered_map<int, int> check;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n;
 
    int maxDate = 0;
    for (int i = 0; i < n; ++i)
    {
        cin >> a >> b;
 
        nodes.push_back({ a,b });
        dates.push_back(b);
        maxDate = max(maxDate, b);
    }
 
    sort(nodes.begin(), nodes.end(), cmp);
 
    int dateIndex = 0;
    int sumMoney = 0;
 
    for (int i = maxDate; i >= 1; --i)
    {
        while (dateIndex < n && nodes[dateIndex].date >= i)
        {
            pq.push(nodes[dateIndex].price);
            ++dateIndex;
        }
 
        if (!pq.empty())
        {
            sumMoney += pq.top();
            pq.pop();
        }
    }
 
    cout << sumMoney;
}
 

 

바로 이전에 풀었던 보석도둑의 풀이법을 응용해서 풀었다.

완전 그대로 적용되는 문제는 아니고, 보석도둑문제를 잘 이해했다면 풀 수 있는 문제다.

 

이 문제에서 주어지는 d값, 즉 날짜는 해당 날짜'까지'이다. 즉, d값이 5라면 첫번째날에 해당강연을 해도되고 두번째날,세번째날,네번째날,다섯번째날까지 하나를 선택하는게 가능하다.

1~5로 하면 d값이 1,2,3,4인것들이랑 겹치니까, 주어진 d값이 유일하게 되는 경우를 생각해본다.

그냥 값 그대로 5일에 할 수 있는 강연은 d값이 5인것밖에없다. 

 

그러니 최대날짜(주어진 날짜값들 중 가장 큰값)을 시작으로, -1씩 하면서 아래로직을 수행한다.

1. 현재 인덱스값(현재날짜)값 이상의 날짜를 가진 강연을 우선순위큐에 전부 넣는다.

2. dateIndex값을 ++한다. 헷갈릴가봐 말하는데, 강연들정보 담은 nodes는 날짜기준으로 내림차순했기 때문에 index를 0부터 시작하는것이다. 헷갈리면 그냥 날짜값처럼 큰거부터 접근하게 오름차순정렬하고 dateIndex를 maxIndex-1로 잡고 -- 하면 된다.

3. 우선순위큐가 안비었으면 top값을(가격이 가장 큰값)을 정답에 누적시킨다.

 

이때, 유의해야할 점은 maxDate를 기준으로 0까지 전부 순회해야한다는것. 

문제에서의 인풋에 주어진 날짜가 1,2,5,10 이면 10부터 9,8,7,6,5,4,3,2,1 을 전부 체크해줘야한다.

왜냐하면 강연의 d값이 10이라는것은, 10일 이내에 강연할 수 있다는 것이고 그 말은 최대값이 10일경우 언제든지 강연할 수 있다는 것이기 때문이다.

그렇기 때문에 만약 (30,10) , (50,10), (10,9) 가 주어질 때,  d값은 똑같이 10인데 p값이 다를경우 36행에서의 i값이 10일때는 p값이 50인걸 넣고 이걸 뽑아서 sum에 누적시킬 것이다.

그다음 i가 9일 때, 여전히 (30,10)을 뽑을 수 있게해야한다. 왜? d값이 10이라는것은 말했다시피 10일이내면 언제든지 뽑을 수 있다는거니까...