백준 2841 외계인의 기타 연주 c++ [컴공과고씨]

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

2841번: 외계인의 기타 연주

이 문제 같은 경우 각 줄마다 누루고 있는 음을 저장하는 스택배열을 선언해서 풀면 쉽게 풀 수 있다.

 

음을 누를경우 스택에 넣어준다. 이유는 먼저 누른 음은 항상 나중에 뗄 것이기 때문이다.

만약 5를 누루고 10을 누루고 11을 눌렀다고 치고 6을 누르려고 하면 손가락을 뗄 때는 마지막에 누른 음부터 손가락을 떼게 된다. 11->10까지 떼주고 6을 눌러준다. 그렇기 때문에 스택을 이용해주면 된다.

 

단계별 풀이

1. 아무것도 누르고 있지 않을 때는 원하는 음을 스택에 추가하고 움직임 +1

2. 만약 스택의 top 값이 누르고 싶은 음보다 더 작다면 그냥 눌러주면 됨 -> 스택에 넣어주고 움직임 +1

3. 만약 스택의 top 값이 누르고 있는 음보다 더 크다면 손을 떼주는 작업을 해야함.

3-1. 원하는 음보다 더 작은 값이 나올때 까지 손을 떼고 뗄때마다 움직임 +1

3-2. 만약 떼다가 전부 다 뗀 상태가 된다면(누르고 있던 음들이 누를려고 하는 음보다 모두 컸을 경우) 스택에 넣어주고 움직임 +1

3-3. 떼다가 스택의 top값이 더 작은 경우 스택에 추가 하고 움직임 +1

 

전체코드

#include <iostream>
#include <stack>
using namespace std;
stack<int> s[8];
int main(){
    int n, p;
    cin >> n >> p;
    
    int a,b;
    int ans = 0;
    for (int i = 0; i < n; i++){
        cin >> a >> b;
        if(s[a].empty()){ // 아무것도 누르지 않고 있을 때
            s[a].push(b); // 눌러줌
            ans++; // 움직임 추가
        }
        else if(s[a].top() < b){ // 누르고 있는 음보다 높은 것을 누를때
            s[a].push(b); // 눌러줌
            ans++; // 움직임 추가
        }else if(s[a].top() > b){ 
            // 치고 싶은 음이 누르고 있는 음보다 작을때
            while(s[a].top()>b){
                s[a].pop(); // 음이 나올때 까지 손을 때 줌.
                ans++; // 움직임 추가
                if(s[a].empty()){ 
                // 누르고 있는 음 전부가 치고 싶은 음보다 낮을 때
                    s[a].push(b); // 전부 손을 떼고 눌러줌
                    ans++; // 움직임 추가
                }
            }
            if(s[a].top() < b){ 
            //손을 떼다 누루고 있는 음이 치고 싶은 음 보다 더 작을때
                s[a].push(b); // 눌러줌
                ans++; // 움직임 추가
            } 
            // 손을 떼다 누르고 있는 음이 치고있는 음과 같을 때는 움직임 추가가 없어도됨.
        }
    }
    cout << ans;
    return 0;
}

체감 난이도	걸린시간	참고	사용 문법
중하	29min	x	stack