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

문제

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

2841번: 외계인의 기타 연주

접근

외계인이 기타를 칠 때 손가락을 최소로 움직인 횟수를 구하는 문제이다. 이때 외계인은 손가락이 무수히 많기 때문에 손가락의 개수는 따로 고려하지 않아도 된다. 따라서 6개의 기타 줄을 누르고 있는 프렛의 수를 비교해가며 손가락을 떼거나 누르면 된다. 즉 stack의 구조로 쉽게 해결할 수 있다.

현재 눌러야 하는 프렛의 번호가 이미 눌려있는 프렛의 번호보다 크면 그냥 손가락을 하나 더 써서 또 눌러주면 되고, 아니라면 현재 눌러야 할 수보다 작은 수가 나올 때까지 손을 떼주면 된다. 이 과정에서 더는 줄을 누르고 있는 손가락이 없거나(stack size 0) 현재 눌러야 할 프렛 번호를 만날 수(stack의 top 값이 현재 값과 같다)도 있음으로 적절히 예외처리해 준다.

 

코드

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n, p, a, b, answer = 0;
    cin >> n >> p;
    vector<int> s[10];
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        if (s[a].size() == 0) {
            s[a].push_back(b);
            answer++;
        } else {
            if (s[a].back() == b)
                continue;
            else if (s[a].back() < b) {
                s[a].push_back(b);
                answer++;
            } else {
                while (1) {
                    if (s[a].size() == 0 || s[a].back() < b) {
                        s[a].push_back(b);
                        answer++;
                        break;
                    } else if (s[a].back() == b)
                        break;
                    s[a].pop_back();
                    answer++;
                }
            }
        }
    }
    cout << answer;
}

 

깃 허브 주소 : https://github.com/algoribi/algorithm-study