[BOJ] 2841 외계인의 기타 연주

문제: https://www.acmicpc.net/problem/2841

설명: 항상 가장 높은 플랫만이 연주된다는 점에서 실마리를 찾아볼 수 있다. 어떤 줄 A에 만약 B의 음을 연주해 달라는 쿼리가 들어왔다고 하자.

1. 현재 그 줄에 누르고 있는 손가락이 없는 경우

이 경우에는 당연히 주어진 음에 해당하는 손가락을 누르고 음을 연주하면 된다. 이때 손가락을 한번 누른다.

2. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어진 음과 같은 경우

손가락을 따로 움직일 필요 없이 그냥 음을 연주하면 된다.

3. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어진 음보다 낮은 경우

주어진 음에 해당하는 플랫을 누르고, 그 다음 음을 연주하면 된다

4. 현재 그 줄에 누르고 있는 가장 높은 손가락이 주어진 음보다 높은 경우

이러면 주어진 음보다 높은 음에 해당하는 곳을 누르고 있는 모든 손가락을 떼야 한다.

그러면 상황은 1, 2, 3번 중 하나의 케이스에 해당할 것이므로 그렇게 처리하면 된다.

복잡해 보이지만 소스코드는 굉장히 간단하다.

 2, 3번과 4번을 따로 분리할 필요가 없다는 점과, 스택이 비었을때 top 연산을 실행하는 등 발생할 수 있는 언더플로우 에러를 맨 처음 모든 스택에 0을 삽입해 줌으로서 깔끔하게 해결하는 점에 주목하자.

체감 난이도는 1.5/5?

#include <cstdio>
#include <stack>
 
using namespace std;
 
int main()
{
    int n,p,s=0;
    stack<int> S[7];
    scanf("%d %d",&n,&p);
    for(int i=1; i<=6; i++)
        S[i].push(0);
    while(n--)
    {
        int t1,t2;
        scanf("%d %d",&t1,&t2);
        while(S[t1].top()>t2)
        {
            S[t1].pop();
            s++;
        }
        if(S[t1].top()!=t2)
        {
            S[t1].push(t2);
            s++;
        }
    }
    printf("%d",s);
    return 0;
}