백준, BOJ, 2841번, 외계인의 기타 연주 : C++ [CPP]

그냥 문제 이해가 조금 어려웠다.

 

 

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

 

---

#맞는 풀이

#include <iostream>
#include <stack>
#include <vector>

using namespace std;

int N, P;


stack<int> vec[7];


int main(){
    cin >> N >> P;
    int cnt = 0;
    for(int i = 0; i<N; i++){
        int x, y;
        cin >> x >> y;

        //먼저 누르려는 것보다 아래를 연주하려는지 확인
        while(!vec[x].empty()){
            //가장 위 플랫을 제거
            if(vec[x].top()>y){
                cnt++; 
                vec[x].pop(); 
            }else break;

        }
        //손을 다 뗀 후에
        
        //이미 누른 상태면 그냥 패스
        if(!vec[x].empty()){
            if(vec[x].top() == y)continue;
        }    
            
        //안눌렀다면 눌러야함
        vec[x].push(y);
        cnt++;


    }
    
    cout << cnt;
    
    return 0;
}

 

 

그니까 가장 높은 플랫이 항상 연주되니까

낮은 플랫을 연주하고 싶을 때는 앞서 눌러져있는 모든 플랫을 떼어야 한다.

뗼 떼는 가장 나중에 눌렀던(가장 높은 플랫) 부터 뗀다.

여기서 자료구조를 힙 또는 스택으로 구현할 수 있으나 맥스힙으로 굳이 구현할 필요가 없다.

왜냐하면 항상 입력도 최댓값만 입력이 되기 때문이다.

 

그래서 스택으로 풀었고 C++에서 if 문에서 조건이 2가지 이상이 들어갈 때

더군다나 AND 문일 때는 한가지만 삑사리나도 해당 statement를 실행하지 않는데..

C++에서는 if문의 모든 조건을 조사해보기 때문에 empty 조건과 top 조건을 따로 조사해야 한다.