BOJ 2304번: 창고 다각형

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

2304번: 창고 다각형

아... 정말 어려웠다... 사실 어려운 것보다 내가 너무 어렵게 생각했던 것 같다.

 

처음에는 주어진 입력을 각각 원소로 해서 2차 배열을 만들어 저장하고 maxHeight를 찾고 그걸 기준으로 어떻게 잘 나누어서 해보자.. 라고 접근을 했는데 이 방식도 계속 파고 들어가면 풀 수 있을 것 같긴 하나.. 이렇게 푸는 게 과연 맞는 건가 하는 의문이 계속 들었다.

 

그리고 나서는 아, 그럼 maxHeight와 그때의 index도 같이 구해서 인덱스로 접근을 해볼까? 하고 생각했는데 그러자니 내가 받은 2차배열에 접근하는 것이 어려웠다.

 

검색의 힘을 빌린 결과.. 그렇다면 처음에 배열을 입력받을 때 L을 그냥 인덱스로 하여 1차 배열로 값을 받으면 되는 것이었다...ㅠㅠ 왜 이런 생각을 하지 못했을까.

 

그리하여 아무튼,, maxHeight의 index를 기준으로 오른쪽과 왼쪽을 나누고 (제일 처음 나오는 기둥의 인덱스이다.) 각각 maxHeight의 index를 향하는 방향으로 탐색하면서 큰 값이 나올 때마다 stack에 push 해준 후, stack의 top을 정답에 더해나가는 방식으로 구현하였다. pop은 꼭 하지 않아도 괜찮았다. 스택 문제라기보다는 구현 문제에 가까운 것 같다.

 

import sys

N = int(sys.stdin.readline())
arr = [0]*1001
maxH = -1
maxL = -1
end = -1

for _ in range(N):
    l, h = map(int, sys.stdin.readline().split())
    arr[l] = h
    if (maxH<h):
        maxH = h
        maxL = l
    end = max(end, l)

ans = 0
stack = []
stack.append(0)

for i in range(0, maxL+1): #오른쪽
    if (stack[-1] < arr[i]):
        #stack.pop()
        stack.append(arr[i])
    ans += stack[-1]

stack.append(arr[end])
for i in range(end, maxL, -1): #왼쪽
    if (stack[-1] < arr[i]):
        #stack.pop()
        stack.append(arr[i])
    ans += stack[-1]

print(ans)