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

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

2841번: 외계인의 기타 연주

 

문제 해결

n과 p가 매우 크기 때문에 dp를 사용하기는 부담스럽다. (dp는 주어진 숫자보다 큰 것을 모두 봐야하기 때문)

따라서 stack을 1~6번 스택을 만들고 FIFO 방식으로 들어가거나 나간 횟수 계산을 하는 것이 편하다.

 

CODE

import sys
input = sys.stdin.readline

n, p = map(int, input().split())
stack = [[] for _ in range(7)]
ans =0
for _ in range(n):
    a, b = map(int, input().split())
    while len(stack[a]):
        if stack[a][-1] > b:
            stack[a].pop()
            ans += 1
        else:
            break
    if len(stack[a])!=0 and stack[a][-1]==b: continue
    stack[a].append(b)
    ans += 1
print(ans)