[백준] 2841 : 외계인의 기타 연주

www.acmicpc.net/problem/2841

2841번: 외계인의 기타 연주

---

• 문제 설명이 꽤나 장황하지만, 결국에는 한 줄마다 내가 이번에 누를 위치보다 높은 값이 있으면 안된다는 것이다.
• 단순하게 생각해서, 우선순위 큐를 두어서 내가 프렛을 누를때마다 최고값이 오게끔 한 뒤 매번 눌렀다 뗐다 해주면 된다.
• priority_queue 에서 애초에 비어 있을 때 top 을 하면 에러가 나지만, while 문에서 pop 을 통해 비워지면 큐에서 캐싱하는 듯한 마지막 값이 top 으로 계속 찍히고, 큐의 사이즈를 봐도 언더플로우 같았다. 개발자 의도인지 에러인지는 모르겠다.
• 사실 손가락이 5개라는 점도 검사를 해야 할 것 같지만, 테스트케이스의 입력값을 잘 넣어놓은건지, 그것까지 문제에서 고려하고 있지 않은지는 잘 모르겠다.
• 이외에도 프렛의 간격에 따라 물리적으로 불가능한 조건들도 가능하다고 생각하는데, 더 어렵게 만들 수 있는 여지가 보인다.

---

#include <iostream>
#include <queue>

using namespace std;

int N, P;
int line, pret, count = 0;
priority_queue<int> pq[7];          // 6개 줄에 대한 각각의 우선순위큐

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> P;
    for(int i = 0 ; i < N ; i++)
    {
        cin >> line >> pret;

        while(!pq[line].empty() && pq[line].top() > pret)   // 이번에 누를 프렛보다 높은 프렛이 있으면
        {
            pq[line].pop();                                 // 손가락을 다 뗀다
            count++;
        }
        if(!pq[line].empty() && pq[line].top() == pret) continue;   // 만약 같은 프렛이면 누를필요 없으니 건너뛴다
        
        pq[line].push(pret);                               // 눌러야 하는 프렛이라면 눌러준다
        count++;
    }

    cout << count << endl;
}