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

티스토리 뷰

tose33 2023. 2. 10. 15:17

2841번: 외계인의 기타 연주

첫째 줄에 멜로디에 포함되어 있는 음의 수 N과 한 줄에 있는 프렛의 수 P가 주어진다. (N ≤ 500,000, 2 ≤ P ≤ 300,000) 다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수

www.acmicpc.net

priority_queue<int> pq[7] 의 max heap 우선순위 큐를 만들어서 각 줄마다 프렛을 넣어준다.

max heap 이므로 top에 가장 높은 fret 이 온다.

새로운 fret 보다 큰 fret은 모두 빼주고 빼줄때마다 손가락을 움직이는 것이므로 answer을 증가시킨다.

주의할점은 pq의 top에 새로운 fret 과 같은 fret이 있으면 손가락을 움직이지 않아도 된다.

그런데 풀고보니까 그냥 스택 써도 된다 ㅋㅋ .

공지사항

최근에 올라온 글

최근에 달린 댓글

링크

글 보관함