[백준] 6198 옥상 정원 꾸미기 C++

1. 문제 설명

• 문제 바로가기

---

2. 풀이 과정

• 문제 해결의 흐름 

    1. 2493 탑 문제와 굉장히 비슷하지만 이 문제는 이전에 추가된 자료가 아닌 새롭게 추가된 자료에 대해 조건을 걸어주어야할듯 하다!

    2. 새롭게 추가되는 빌딩의 높이가 직전에 추가된 빌딩의 높이보다 높거나 같다면 이전에 추가된 빌딩의 관리자는 새롭게 추가된 빌딩을 보지 못한다.

    3. 쉽게 생각해본다면 이전에 추가된 빌딩들보다 낮은 높이의 빌딩이 추가된다면 계속 빌딩을 볼 수 있다.

    4. 반면, 이전 빌딩보다 높이가 높거나 같은 빌딩이 추가된다면 이전 빌딩의 관리자는 더 이상 추가되는 빌딩을 볼 수 없기에 삭제해주어야 한다.

    5. 이 문제 역시 새롭게 추가되는 자료와 이전에 추가된 자료에 대해 관심이 깊으니 후입후출이라는 단서를 파악하여 stack을 사용하여 풀어보자!! 

 

• 코드 

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;

    stack<int> S;
    long long result = 0;
    for (int i = 0; i < N; ++i) {
        int curHeight;
        cin >> curHeight;

        while(!S.empty()) {
            if (S.top() > curHeight) {
                result += S.size();
                S.push(curHeight);
                break;
            }
            S.pop();
        }

        if (S.empty()) {
            S.push(curHeight);
        }
    }

    cout << result;

    return 0;
}

---

3. 후기 

 로직 자체는 '2493번 탑' 문제와 굉장히 비슷하여 쉽게 풀릴줄 알았지만 이상하게 계속 '틀렸습니다'가 떴다.. ㅠㅠㅠ
 알고 보니 빌딩의 개수 N은 8만 이하의 수이다. 따라서 출력되는 최대 값은 1부터 (8만-1)까지 더한 값인데 이 값은 약  5.76 x 10**17이다. 이 값은 int로 담을 수 없기에 long long으로 담아주었다!
 사용하는 자료형으로 값을 담을 수 있을지 없을지 확인해주는게 중요함을 깨달았다!