[BOJ 2841] 외계인의 기타 연주

문제는 여기서 풀 수 있습니다.

문제 요약

여섯 개의 줄을 가진 기타가 있고 각 줄은 $P$개의 플랫을 가지고 있습니다.

기타 연주를 할 때 한 줄에 여러 개의 플렛을 누르고 줄을 튕기면 그중 가장 높은 플랫이 연주됩니다.

플랫을 누르거나 떼는 것을 손가락이 한 번 움직였다고 했을 때 주어진 악보를 최소한의 손가락 움직임으로 연주하고 싶습니다.

연주자는 상상 속의 외계인이라서 수십억 개의 손가락을 가져 모든 플랫을 동시에 누를 수 있습니다.

문제 풀이

여섯 개의 줄을 가진 기타지만 각각의 줄은 서로 다른 줄에 영향을 미치지 않습니다. 따라서 한 개의 줄에 대해서 최소한의 손가락 움직임 횟수를 알아낼 수 있다면 여섯 개의 줄의 답을 각각 구한 뒤 더하면 문제에서 원하는 답을 찾을 수 있습니다.

한 개의 기타 줄에서 플랫을 누르거나 떼야 할 상황은 두 가지가 있습니다.

1. 전보다 플랫이 높아지는 경우
2. 전보다 플랫이 낮아지는 경우

첫 번째 상황에서는 전에 누르고 있던 플랫을 누른 채 새로운 플랫을 누르는 것이 최선입니다. 누르고 있던 플랫보다 더 높은 플랫을 누른 채 줄을 튕기면 더 높은 플랫이 연주되기 때문입니다. 계속해서 전보다 높은 플랫이 나온다면 기타 줄에서 누르고 있는 플랫은 점점 더 많아질 것입니다.

두 번째 상황에서는 전에 누르고 있던 플랫들이 현재 눌러야 할 플랫보다 높아서 현재 플랫보다 높은 플랫들에서 전부 손을 떼야 합니다.

이 두 가지 아이디어는 스택을 이용해 쉽게 구현할 수 있습니다. 따라서 이 문제는 $O(N)$에 풀 수 있습니다.

#include <stdio.h>
#include <stack>

using namespace std;

int n, p, ans, num, flat;
stack<int> lines[6];

int main() {
	scanf("%d%d", &n, &p);

	while (n--) {
		scanf("%d%d", &num, &flat);

		auto& line = lines[num - 1];
		while (!line.empty() && line.top() > flat) {
			++ans;
			line.pop();
		}

		if (line.empty() || line.top() < flat) {
			++ans;
			line.push(flat);
		}
	}

	printf("%d\n", ans);
}