[BOJ/백준 2841][C++] 외계인의 기타 연주

문제

https://www.acmicpc.net/problem/2841

문제 내용

기타로 멜로디를 연주할 때, 가장 손가락을 적게 움직이는 방법을 찾으면 된다.

stack을 사용하여 이 문제를 풀면 좋다.

 

문제 풀이

1~6번 줄을 각각 스택으로 선언한다.

두 번째 줄부터 입력 형식이 (줄 번호, 프렛 번호) 이므로, 해당 줄 번호 스택에 프렛 번호를 추가하면 된다.

 

이때 고려할 사항이 몇 가지  존재한다.

1. (이미 누르고 있는 프렛 번호) < (누르려는 프렛 번호)

이 경우 그냥 스택에 새로운 프렛 번호를 추가해주면서, count 개수도 1 증가시키면 된다.

 

2. (이미 누르고 있는 프렛 번호) == (누르려는 프렛 번호)

별 다른 처리가 필요하지 않다.

손가락을 움직일 필요도, 스택을 변화시킬 이유도 없다.

 

3. (이미 누르고 있는 프렛 번호) > (누르려는 프렛 번호)

이 경우가 가장 처리할 것이 많다.

내가 소리 내고자 하는 프렛 번호가 더 낮기 때문에, 누르려는 프렛 번호보다 높은음은 모두 손가락을 떼야한다.

그렇기 때문에 반복문을 통해 스택에서 제거하는 과정이 필요하다.

스택에서 누르려는 프렛 번호보다 높은 프렛을 전부 제거했다면, 위의 1~2 중에 해당되는 과정을 실행하면 된다.

 

참고로 스택이 비어있을 때, top(), pop() 함수를 실행하면 에러가 난다.

따라서 1~3번을 진행할 때 empty() 체크를 해야 한다.

 

코드

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


int main() {
	//기타 => 줄 6개, 각 줄마다 프렛 P개

	//입력
	int n,p;
	cin >> n >> p;
	vector<stack<int>>v(7); //줄:1~6번
	
	//문제 해결
	int count = 0;
	for (int i = 0; i < n; i++) { //입력받는 음의 개수
		int line, pp;
		cin >> line >> pp;
		
		//비어있지 않고, 손을 떼야 할때 (3번)
		if (!v[line].empty() && v[line].top() > pp) { //비어있는데 top()하면 에러
			while (!v[line].empty() && v[line].top() > pp) {
				v[line].pop();
				count++;
			}
		}

		//추가하기 (1번)
		if (v[line].empty() || v[line].top() < pp) { 
			count++;
			v[line].push(pp);	
		}
        
        //v[line].top() == pp인 경우(2번)는 어차피 처리할 것이 없으므로 코드를 안 짜도 된다.
	}
	
	//결과 출력
	cout << count << '\n';
}

 

문제 코드 설명

1) 입력

기타의 줄이 6개이고, 각각의 줄마다 스택이 필요하므로 vector <stack <int>>v(7); 로 선언을 했다.
이때 7개를 선언한 이유는 줄번호를 입력받는 그대로 쓰기 위함이다. (0부터 카운팅하면 머리 아프기 때문)

 

2) 문제 해결

이 부분은 경우를 잘 나누어 생각하면 문제될 것이 없다.

다만 조건을 확인하는 부분에서 v[line].top()을 사용하게 되는데, top() 함수는 스택이 비어있으면 에러가 나기 때문에 반드시 empty() 확인을 먼저 해주어야 한다.