[백준/2841/파이썬] 외계인의 기타 연주

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

2841번: 외계인의 기타 연주

조건

• 상근이는 손가락이 수십억개인 상상의 친구를 갖고있다. (무섭다)
• 기타 : 1~6번줄, P개의 프렛이 있음.
• 각줄에 해당하는 프렛을 누르고, 줄을 튕기면 연주할 수 있음.
• 어떤 줄의 프렛을 여러개 누르고있따면, 가장 높은 음이 발생한다.
• 예를 들어, 3번 줄의 5번 프렛을 이미 누르고 있으면, 7번 프렛을 누른 음을 연주하려면, 5번 프렛을 누르는 손을 떼지 않고, 다른 손가락으로 7번 프렛을 누르고 연주하면 됨.
• 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한번 움직였다고 한다.

항상 이런 문제를 보면, 이해가 잘 안간다.

입력

INPUT

5 15

2 8

2 12

2 10

2 5

OUTPUT

7

 

이렇게 나오는데, 사실 이해가 안감.

2 8 - 1번

2 10 ( 8을 누른 상태로 , 10을 누르면 되니까 프렛 10을 누름. ) 1번

2 12 ( 8.10을 누른 상태로 12를 누르면 됨.) 1번

2 10 ( 12를 떼면됨) - 1번

2 5 - 10을 떼고, 8을 떼고, 5를 누르면 - 3번

이렇게 해서 7번 ?

1 5 - 1번

2 3 - 5번을 떼고, 3번을 눌러야함 . - 2번- ⇒ 2 번줄 3번을 누르면 됨. 1번

2 5 - 3에서 5번만 누르면 됨 1번

2 7 - 3,5 누른 상태에서 7번 누르면 됨 1번

2 4 - 7번 떼고, 5번떼고, 4번 누르면 됨. 3번

1 5 - 4번에서 5번만 누르면 됨 . 1번 ⇒ 1번줄에 5번은 누르고 있으니 PASS

1 3 - 5번떼고 4번떼면됨. 2번

10번..

뭔가 이상하다. 다른 줄 일때는 , 다르게 생각 해줘야 하는건가 !?

역시, 다른 줄에 있는거면 다른걸로 생각해줘야한다.

SOL)

제일 먼저 떠오르는건 ,스택이다. 스택에 PUSH,POP하는 과정이 기타줄을 떼고, 누르고 하는거랑 같고, 6개의 줄이니까, 스택 6개를 마치, 기타 줄 처럼 생각하면 편할거 같다.

push,pop 명령 둘다 기타 줄에서 손을 누르고, 떼는거기 때문에 카운트 해줘야한다.

input 값과 stack의 top값을 비교해서, top값이 크면, push 하고 input 값이 작으면,

input 값이 클때까지 push하고, 마지막에 push해준다.

 

n,p = map(int,input().split())
note = [list(map(int,input().split())) for _ in range(n)]

cnt=0
guitar=[[] for i in range(7)] # 6개의 스택 생성.

for line,plot in note:
	if not guitar[line]:
		guitar[line].append(plot) # 기타 해당 줄이 비어있으면 ,PUSH
		cnt+=1
	else:
		if guitar[line][-1] < plot:
			guitar[line].append(plot)
			cnt+=1
		elif guitar[line][-1] == plot:
			continue;
		else:
			while not guitar[line] and guitar[line][-1] > plot: # 기타라인에 플롯이 있고, guitar의 TOP이 PLOT보다 작을때 까지, 계속 POP
				guitar[line].pop()
				cnt+=1
			if not guitar[line] and guitar[line][-1] == plot:
				continue
			guitar[line].append(plot) # 다 빼주고 난다음에 , 자기 자신 넣어야함.
			cnt+=1
print(cnt)

#이런 느낌일거 같아용!