[BOJ/Gold 5] 백준 30470 호반우가 학교에 지각한 이유 3(C++)

문제 링크

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

30470번: 호반우가 학교에 지각한 이유 3

 

문제

우여곡절 끝에 시작의 마을 앞까지 도착한 호반우지만 절벽 위의 마을로 향하는 계단이 마물들의 습격으로 망가져 통나무로 계단을 만들기로 하였다. 호반우는 통나무를 세로로 나란히 세워 계단을 만드는데, 중간중간 마물들이 마법을 사용해 방해하고 있다!

마물들이 위력이 m인 마법을 사용하면, 현재 계단을 구성하는 통나무 중 가장 긴 통나무의 길이 k를 기준으로 길이가 max(k - m, 0) 이상인 통나무들의 길이를 max(k - m, 0)으로 만들어 버린다. 만약 통나무가 없다면 마법은 무시한다.

호반우와 마물들의 행동을 나타내는 N개의 쿼리가 다음과 같이 주어진다.

• 1 x: 호반우가 길이 x의 통나무를 계단 옆에 나란히 세운다.
• 2 x: 마물들이 계단에 위력 x의 마법을 사용한다.

호반우는 계단을 만들고 싶기에 호반우가 새로 세우는 통나무는 항상 이전에 1번 쿼리로 세운 통나무의 길이보다 길며, 마물들은 통나무가 없어도 마법을 사용할 때가 있다. 호반우가 처음으로 세우는 통나무는 따로 길이의 제한이 없다.

 N개의 쿼리를 순서대로 전부 수행한 이후 완성된 계단을 구성하는 모든 통나무의 길이의 합을 구해보자.

 

입력

첫 번째 줄에 쿼리의 개수 N이 주어진다. (1 ≤ N ≤ 500,000)

두 번째 줄부터 N개의 줄에 걸쳐 양의 정수 쌍 a, b가 공백을 두고 주어진다. (a ∈ {1, 2}, 1 ≤ b ≤ 10^9)

 a가 1이면 호반우가 길이 b의 통나무를 계단 옆에 세운 것이고 새로 세우는 통나무는 항상 이전에 1번 쿼리로 세운 통나무의 길이보다 길다.

 a가 2이면 마물들이 계단에 위력 b의 마법을 사용한 것이며 계단을 구성하는 통나무가 없는 상태에서도 2번 쿼리가 입력될 수 있다.

 

출력

 N개의 쿼리를 순서대로 전부 수행한 이후 완성된 계단을 구성하는 모든 통나무의 길이의 합을 출력한다.

 

예제 입력 1

3
1 2
2 1
1 4

예제 출력 1

5

예제 입력 1

5
1 4
1 7
2 5
1 11
2 2

예제 출력 1

13

 

알고리즘 분류

• 자료 구조
• 시뮬레이션

 

풀이

A가 1이면 스택의 top에 B를 push한다.

A가 2이면 스택이 비어 있지 않은 경우 스택의 top을 max(top - B, 0)으로 초기화한다.

N번의 쿼리문을 수행한 후 마지막으로 스택이 비어 있지 않은 경우, 스택의 top을 가장 긴 길이로 정하고, 해당 길이를 기준으로 다음과 같이 통나무의 길이를 정한다.

• 현재 통나무의 길이가 top보다 길면 현재 통나무의 길이는 마법에 걸려 길이가 top으로 바뀐 것이다. 따라서 길이를 top으로 취급한다.
• 현재 통나무의 길이가 top과 동일하면 그냥 넘어간다.
• 현재 통나무의 길이가 top보다 짧으면 top을 현재 통나무의 길이로 초기화한다.

 

이렇게 통나무의 길이를 정하고 길이의 총합을 구한다.

 

코드

#include <iostream>
#include <vector>
#include <string>
#include <stack>
#include <algorithm>
#define LL long long
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N;
LL A, B;
stack<LL> S;
LL Answer;

void make_tree() {
    S.push(B);
}

void use_magic() {
    LL K = S.top();
    S.pop();
    S.push(max(K - B, (LL)0));
}

void input() {
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A >> B;
        if (A == 1) {
            make_tree();
        }
        else {
            if (!S.empty()) {
                use_magic();
            }
        }
    }
}

void settings() {
    LL Top = S.top();
    while (!S.empty()) {
        LL Now = S.top();
        if (Now > Top) {
            Answer += Top;
        }
        else if (Now < Top) {
            Top = Now;
            Answer += Now;
        }
        else {
            Answer += Now;
        }
        S.pop();
    };
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    if (!S.empty()) {
        settings();
    }
    find_Answer();

    return 0;
}