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

문제

1번부터 6번 줄이 있는 기타가 있다.

기타의 한 줄에는 P개의 프렛으로 나누어져있고 프렛도 1번부터 P번까지 번호가 있다.

어떤 줄의 프렛을 여러 개 누르고 있다면 가장 높은음만 출력된다.

손가락으로 프렛을 한 번 누르거나 떼는 동작이 손가락을 한 번 움직였다고 했을 때 어떠한 멜로디를 연주하는데 손가락을 가장 적게 움직이는 횟수를 구하라

 

입력

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

다음 N개 줄에는 멜로디의 한 음을 나타내는 두 정수가 주어진다. 첫 번째 정수는 줄의 번호이고 두 번째 정수는 그 줄에서 눌러야 하는 프렛의 번호이다. 입력으로 주어진 음의 순서대로 기타를 연주해야 한다.

 

출력

첫째 줄에 멜로디를 연주하는데 필요한 최소 손가락 움직임을 출력한다.

---

접근

스택에는 가장 최근에 넣은 데이터가 상단에 위치하기때문에 이를 활용한다.

현재 입력한 어떤 줄의 프렛을 스택의 TOP과 비교하여 누를지 말지 처리를 하도록 하자.

 

구현

- 1번부터 6번까지의 줄을 갖는 스택을 생성한다.

- N개의 멜로디를 입력받아 line과 p에 저장한다.

- 해당 line의 스택이 비어있다면 p를 누른다.

- 하지만 비어있지 않다면 스택의 top과 p를 비교한다.

- p가 더 크다면 이전에 누른 것을 뗄 필요가 없기 때문에 push만 해주고 최종해를 증가시킨다.

- 또한 같은 음일 때는 누를 필요도 없기 때문에 바로 continue한다.

- 이어서 현재 누른 p보다 높은 음일 때는 작은 음이 나올 때까지 pop을하면서 최종해를 증가시킨다.

#include<iostream>
#include<algorithm>
#include<stack>
#include<string>
#include<cstring>
using namespace std;


int main()
{
	int N, P;
	int answer = 0;
	stack<int> st[7];
	cin >> N >> P;
	for (int i = 0; i < N; i++) {
		int line, p;
		cin >> line >> p;

		if (st[line].empty()) {
			st[line].push(p);
			answer++;
		}
		else {
			if (st[line].top() < p) {
				st[line].push(p);
				answer++;
			}
			else if (st[line].top() == p) {
				continue;
			}
			else {
				while (!st[line].empty()) {
					if (st[line].top() <= p)
						break;
					st[line].pop();
					answer++;
				}
				if (!st[line].empty() && st[line].top() == p)
					continue;
				st[line].push(p);
				answer++;
			}
		}
	}
	cout << answer << endl;
	return 0;
}