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

6198번: 옥상 정원 꾸미기

6198번: 옥상 정원 꾸미기

🤔 문제분석

스택 자료구조를 활용하여 문제를 해결한다. 스택은 해당위치에서 자기자신보다 낮은 건물이 나올때까지 꺼낸다. 스택에 담긴 자료는 해당 건물포함해서 그 뒤에 볼 수 있는 건물을 담는다. 자기자신보다 큰 건물이기때문에 해당 건물을 포함한 그 뒤에있는 건물 또한 볼 수 있기때문이다.

💻 코드

import sys
input = sys.stdin.readline

N = int(input())

buildings = list(int(input()) for _ in range(N))

stack = []
ans = 0
for i in range(N-1, -1, -1):
    cnt = 1
    while stack and buildings[i] > stack[-1][0]:
        _, c = stack.pop()
        cnt += c
        ans += c
    
    stack.append((buildings[i], cnt))
    
print(ans)

🎯 피드백 및 개선사항

그리디, 다이나믹 프로그래밍 유형으로 접근하면 쉽게 생각해 낼 수 있는 문제라고 생각합니다. 경비원은 오른쪽만 볼 수 있다는것을 전제하에 접근하면 위와같은 점화식을 도출 할 수 있다.