반갑습니다!

[백준] 6198 옥상 정원 꾸미기 본문

알고리즘 문제 풀이

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

김덜덜이 2020. 4. 2. 01:41

2493 탑과 비슷하게 풀면 된다고 생각했다가 결국 다른 방법으로 풀게 된 문제이다. 스택에 대한 많은 문제를 풀어봐야겠다고 다시 한번 느낀 문제...

풀이

순차적으로 빌딩의 높이 tmp를 입력을 받으며 stack의 데이터를 tmp를 시작으로 내림차순으로 유지하면서 현재 빌딩의 개수를 제외한 값인 stack.size() - 1을 더해주는 것을 반복하면 답을 구할 수 있다.

stack을 내림차순으로 유지하는 방법은 Monothone Stack을 참고하자.

코드

#include <iostream>
#include <stack>
#include <vector>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    long long sum = 0;
    cin >> n;
    stack<int> s;

    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        while (!s.empty() && s.top() <= tmp) s.pop();
        s.push(tmp);
        sum += s.size() - 1;
    }
    cout << sum << '\n';
    return 0;
}

'알고리즘 문제 풀이' 카테고리의 다른 글

[프로그래머스] 2 x n 타일링  (0) 2020.04.02
[프로그래머스] N으로 표현  (0) 2020.04.02
[백준] 2493 탑  (0) 2020.04.02
[프로그래머스] 종이접기  (0) 2020.03.31
[프로그래머스] 호텔 방 배정  (0) 2020.03.31