백준 #1863 스카이라인 쉬운거

코드

import sys
sys.stdin = open("input.txt")
input = sys.stdin.readline

n = int(input())
arr = [list(map(int, input().split())) for _ in range(n)]

stack = [0]
answer = 0
for i in range(n):
    cur = arr[i][1]
    if cur > stack[-1]:
        stack.append(cur)
    else:
        while cur < stack[-1]:
            stack.pop()
            answer += 1
        if stack[-1] != cur:
            stack.append(cur)


while stack[-1]:
    stack.pop()
    answer += 1

print(answer)

풀이

문제를 이해하는데 한참 걸렸다..

위에 예시를 보면 옆으로 이동하면서 만들수 있는 직사각형 개수를 세어주면 된다.

처음에 예시에 표시되어있는 숫자들이 무엇을 뜻하는지 몰랐는데 그냥 만들 수 있는 최대 크기의 직사각형들의 개수를 구해주는 문제였다.

stack에는 처음에 땅을 표시하기 위한 0을 넣어준다

옆으로 움직이면서 stack의 마지막 높이보다 크다면 그대로 넣어주고 작다면 현재 높이보다 큰 stack의 높이들을 pop해주면서 건물 개수를 세어주었다.

만약 모두 pop 해준 후에 stack의 마지막 높이와 현재 높이가 다르다면 stack에 추가해주었다.

그리고 마지막으로 stack에 남아있는 높이가 있다면 건물 개수에 포함시켜주었다!