[백준/구현] 2304: 창고 다각형 - 파이썬

문제

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

2304번: 창고 다각형

 

풀이

그림1 . 기둥과 지붕(굵은 선)의 예

본인이 시도한 풀이는 다음과 같습니다.

1. 먼저 순차적으로 위치별로 기둥의 높이를 리스트에 저장함 (info = [0] * 1001)
2. 리스트에 저장하면서 가장 큰 기둥의 값과 인덱스를 다른 변수에 저장함
3. 처음 기둥부터 가장 큰 기둥까지 좌에서 우로 기둥의 높이가 담긴 리스트들을 탐색한다
4. 리스트를 탐색하면서 높이를 stack에 저장하고 stack의 마지막에 담긴 값을 area에 저장
5. 첫번째 기둥은 높이를 저장할 stack 리스트에 저장함.
6. 탐색중인 해당 기둥 i번째가 i+1번째의 기둥보다 높이보다 높다면  i+1번째 기둥의 높이는 stack에 넣지 않음
7. 기둥 i번째 높이가 i+1보다 낮으면 i+1의 기둥높이를 stack에 저장함.
8. 가장 큰 기둥의 위치 max_high_index까지 반복
9. max_high_index 기준으로 오른쪽으로 마지막까지 3~8 과정을 반복함.
10. 결과값인 area를 출력

 

제출한 풀이

n = int(input())
info = [0] * 1001
max_high = 0
max_high_index = 0
end_index = 0

for i in range(n):
    w, h = map(int, input().split())
    info[w] = h
    if max_high < h:
        max_high = h
        max_high_index = w
    end_index = max(end_index, w)

stack = []
area = 0

for i in range(0, max_high_index+1):
    if not stack:
        stack.append(info[i])
    else:
        if stack[-1] < info[i]:
            stack.append(info[i])
    area += stack[-1]

stack = []

for i in range(end_index, max_high_index, -1):
    if not stack:
        stack.append(info[i])
    else:
        if stack[-1] < info[i]:
            stack.append(info[i])
    area += stack[-1]

print(area)

 

더 짧은 풀이

n = int(input())

rec = [0 for _ in range(1001)]
for _ in range(n):
    l, h = map(int, input().split())
    rec[l] = h
max_idx = rec.index(max(rec))

max_val = 0
for i in range(max_idx):
    max_val = max(max_val, rec[i])
    rec[i] = max_val

max_val = 0
for i in range(1000, max_idx, -1):
    max_val = max(max_val, rec[i])
    rec[i] = max_val

print(sum(rec))