[백준 2841] 외계인의 기타 연주 (C++)

풀이

stack 자료구조를 사용하면 쉽게 해결할 수 있다.

 

줄이 1 ~ 6이므로 stack을 배열처럼 사용하면 여러 개의 stack 줄이 생기게 된다.

현재 top과 치려고 하는 프렛의 번호를 비교해서 count를 매기면 된다.

치려고 하는 프렛의 번호를 b라고 하면

 

top() > b 이면,

pop 해주고 count++

 

top() == b이면,

굳이 손을 다른 프렛으로 옮기지 않아도 되므로 패스

 

top() < b이면,

push 하고 count++

 

#include <iostream>
#include <stack>
using namespace std;

int n, p;
stack<int> st[7];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n >> p;

	int cnt = 0;
	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;

		while (1)
		{
			if (st[a].empty())
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() < b)
			{
				st[a].push(b);
				cnt++;
				break;
			}
			else if (!st[a].empty() && st[a].top() == b)
				break;
			else if (!st[a].empty() && st[a].top() > b)
			{
				st[a].pop();
				cnt++;
			}
		}
	}

	cout << cnt << '\n';
	return 0;
}