백준) 2841 외계인의 기타 연주

외계인의 기타 연주

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

6개의 줄을 가지고 연주를 하는데, 눌러야 하는 줄과 프렛의 번호가 주어진다.

이 때 이미 더 높은 프렛들을 누르고 있었다면 전부 띄어야 한다.

프렛을 누르거나 떼는 과정을 모두 카운트 할 때, 가장 카운트가 적은 방법은 무엇일까?

직관적으로 줄마다 스택으로 생각해서 풀었다.

1번 줄의 5, 7 ,9 를 누르고 있었다면, 1번 줄 스택엔 5, 7, 9가 쌓여있다. 

이 때 6을 누르라는 연주가 주어지면 7과 9를 pop하고 6을 push 한다. 따라서 3의 카운트가 증가한다.

어떤 최소화하려는 전략으로 5까지 떼버리고 6을 누르는 것은 최소의 전략이 아니기 때문이다.

5를 떼는 방법은 다음의 어떤 케이스가 들어와도 누르는 프렛을 유지하는 것보다 카운트가 더 높다.

#include <stdio.h>
#include <stack>
using namespace std;
 
int n, p, a, b, t, ans;
stack<int> sts[7];
 
int main() {
    scanf("%d %d", &n, &p);
    while (n--) {
        scanf("%d %d", &a, &b);
        while (1) {
            if (sts[a].empty()) {
                sts[a].push(b);
                ans++;
                break;
            }
            t = sts[a].top();
            if (b == t) {
                break;
            }
            else if (b > t) {
                sts[a].push(b);
                ans++;
            }
            else {
                sts[a].pop();
                ans++;
            }
        }
    }
    printf("%d", ans);
    return 0;
}