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

金弘均·2021년 9월 16일
0

Baekjoon Online Judge

목록 보기
182/228
post-thumbnail

# Appreciation

/*
 * Problem :: 2841 / 외계인의 기타 연주
 *
 * Kind :: Data Structure
 *
 * Insight
 * - 일단 1번 줄만 있다고 생각해보자
 *   2 3 1 5 9 7 7 프렛을 차례대로 눌러야 한다면
 *   + 누르고 있는 프렛 / 누른 횟수
 *     2            / 1 (push 2)
 *     2 3          / 2 (push 3)
 *     1            / 5 (pop 2,3 push 1)
 *     1 5          / 6 (push 5)
 *     1 5 9        / 7 (push 9)
 *     1 5 7        / 9 (pop 9, push 7)
 *     1 5 7        / 9
 *     # Stack 이네...
 *
 * Point
 * - 각 줄마다 해당하는 스택을 선언해서 다루어주자
 *
 * - 참고로 이미 해당 프렛을 누르고 있는 경우
 *   손가락을 누르거나 떼지 않아도 되는 경우를 고려해주자
 */

# Code

//
//  BOJ
//  ver.C++
//
//  Created by GGlifer
//
//  Open Source

#include <iostream>
#include <stack>

using namespace std;

#define endl '\n'

// Set up : Global Variables
/* None */

// Set up : Functions Declaration
/* None */


int main()
{
    // Set up : I/O
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // Set up : Input
    int N, P;
    cin >> N >> P;

    // Process
    stack<int> st[6+1]; /* 각 줄에 해당하는 스택 선언 */
    int ans = 0; /* 손가락을 움직인 횟수 */
    for (int i=0; i<N; i++) {
        int l, p; /* l = 줄의 번호, p = 프렛의 번호 */
        cin >> l >> p;

        /* p 번 프렛을 누르기 위해서는
         * l 번 줄에서 p 보다 높은 번호의 프렛들을 누르고 있는 손가락을 떼어야 함 */
        while (not(st[l].empty()) && st[l].top() > p) {
            st[l].pop();
            ans++;
        }

        /* l 번 줄에서
         * 현재 누르고 있는 프렛들 중 가장 높은 번호가 p 와 같다면
         * 새로 누르거나 뗄 필요 없이 그냥 줄을 튕기면 됨 */
         if (not(st[l].empty()) && st[l].top() == p) {
             continue;
         } /* 사실상 위의 코드는 실행되어도 답에 아무런 영향을 미치지 않으므로 없애도 무방함 */

        /* l 번 줄에서 누르고 있는 프렛이 없거나
         * 현재 누르고 있는 프렛들 중 가장 높은 번호가 p 보다 작다면
         * p 번 프렛을 새로 눌러야 함 */
        if (st[l].empty() || st[l].top() < p) {
            st[l].push(p);
            ans++;
        }
    }

    // Control : Output
    cout << ans << endl;
}

// Helper Functions
/* None */
profile
이런 미친 게임을 봤나! - 옥냥이

0개의 댓글