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

문제 요약

보통 기타는 1번 줄부터 6번 줄까지 총 6개의 줄이 있고, 각 줄은 P개의 프렛으로 나누어져 있다. 프렛의 번호도 1번부터 P번까지 나누어져 있다.

이렇게 손가락으로 프렛을 한 번 누르거나 떼는 것을 손가락을 한 번 움직였다고 한다. 어떤 멜로디가 주어졌을 때, 손가락의 가장 적게 움직이는 회수를 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 스택

문제 풀이

기타줄이 6개니까 스택을 6개 준비하고, 각 스택의 top에는 가장 높은 값의 프랫이 오도록 하면 된다.

현재 스택의 top보다 높은 프랫의 음을 연주할 경우 그 값을 push하고 cnt를 1더하면 된다.

현재 스택의 top과 같은 프랫의 음을 연주할 경우에는 아무것도 하지 않아도 연주할 수 있다.

현재 스택의 top보다 낮은 프랫의 음을 연주할 경우 그 음보다 높은 프랫들을 모두 pop하면서 cnt역시 그 갯수만큼 1씩 더하면 된다. 마지막의 top의 프랫이 연주하려는 프랫보다 낮으면 현재의 프랫을 push후 cnt를 1증가, 같다면 그대로 연주하면 된다.

풀이 코드

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

using namespace std;

int main()
{
	stack<int> s[6];
	int n, p;
	int cnt = 0;
	int in1, in2;
	cin >> n >> p;
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &in1, &in2);
		if (!s[in1 - 1].empty()){
			while (!s[in1 - 1].empty()) {
				if (s[in1 - 1].top() <= in2) break;
				s[in1 - 1].pop();
				cnt++;
			}
			if (!s[in1 - 1].empty()) {
				if (s[in1 - 1].top() < in2) {
					s[in1 - 1].push(in2);
					cnt++;
				}
			}
			else {
				s[in1 - 1].push(in2);
				cnt++;
			}
		}
		else {
			s[in1 - 1].push(in2);
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}