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

1. 문제

1) 문제 링크

    : www.acmicpc.net/problem/2841

2841번: 외계인의 기타 연주

 

2) 설명

손가락 많은 외계인이 악보대로 기타연주할 때 최소한의 손 움직임을 구하는 문제다.

움직임은 누를 때 1, 뗄 때 1 추가한다

만약 1번줄의 3프렛을 누른 상태에서 1번줄 5프렛을 누르고자 한다면 굳이 3프렛 누른 손을 뗄 필요 없이 5프렛을 바로 누르면 된다. 즉 손 움직임 카운트값이 1 증가한다.

이 상태에서 1번줄 2프렛을 쳐야 한다면 3프렛, 5프렛에 있는 손가락을 모두 떼야 한다. 즉 손 움직임 카운트 값이 2 증가하고 2프렛을 누르면서 총 3 증가하게 된다.

2. 풀이

1) 알고리즘

    : 스택

 

2) 풀이 설명

1번부터 6번 각 줄별로 스택을 만들었다. (총 6개, 스택 라이브러리 대신 벡터를 사용했다. 거의 동일하기 때문에..)

이후 줄별로 연주하는 프렛을 스택에 쌓았고 만약 스택의 마지막 값이 새로 누를 프렛보다 작다면 그냥 1번 스택에 새로 누를 프렛을 넣었다.

만약 스택 마지막 값이 새로 누를 프렛보다 크다면 작은 값이 나올 때까지 계속 스택에서 pop을 해나갔다.(pop 할 때마다 움직임 증가)

이때 스택 초기 선언할 때 원소 하나를 0값으로 넣어서 빈 스택을 참조하는 일을 방지했다. 

 

3. 코드

 

#include <iostream>
#include <vector>
#include <algorithm>

#define LINE_NUM 6
#define MAX_FRET 300000

using namespace std;

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

	int N, P;
	cin >> N >> P;
	int answer = 0;
	vector<vector<int>> stack(LINE_NUM+1, vector<int>(1, 0));

	int line, fret;
	for(int i=0;i<N;i++){
		cin >> line >> fret;
		while(stack[line].back() > fret){
			stack[line].pop_back();
			answer++;
		}
		if(stack[line].back() != fret){
			stack[line].push_back(fret);
			answer++;
		}
	}
	cout << answer << endl;

	return 0;
}

 

4. 느낀점

 - 다른 분들 풀이에 비해 코드 길이는 좀 짧지만 속도가 좀 느렸다.(내 풀이는 88ms, 다른 분들은 80ms)