https://www.acmicpc.net/problem/2304
시간 2초, 메모리 128MB
input :
-
N (1 <= N <= 1,000)
-
기둥의 위치 L(index 처럼 보면 될 듯), 기둥의 높이 H(1 <= L, H <= 1,000)
output : -
창고 다각형의 면적 출력
빗물 구하는 문제와 비슷한 듯.
현재 인덱스 기준 왼쪽에서 큰 item, 오른쪽에서 큰 item 구해서.
작은 item의 높이 와 현재 item 비교한 후에
현재 아이템이 더 크면 total 값엔 현재 아이템을 / 현재 아이템이 작으면 작은 item의 값을 total에 추가한다.
index 0 일때와 마지막 1001일 때를 넣어줘야 할 듯.
빗물 처럼 구하려니... 런타임 에러 계속 박힘/
찾아보니 다들 가장 높이 가 긴 기둥을 중심으로.
왼쪽에서 업데이트.
오른쪽에서 업데이트 하며 채워 감.
import sys
N = int(sys.stdin.readline())
buliding = [0] * 1001
data_list = []
for i in range(N):
L, H = map(int, sys.stdin.readline().split())
buliding[L] = H
data_list.append((L, H))
data_list.sort(key= lambda x:-(x[0]))
last_idx = data_list[0][0]
data_list.sort(key= lambda x:x[0])
start_idx = data_list[0][0]
data_list.sort(key= lambda x:-(x[1]))
biggest_idx = data_list[0][0]
total = 0
idx = start_idx
height = 0
while idx < biggest_idx:
height = max(buliding[idx], height)
total += height
idx += 1
idx = last_idx
height = 0
while idx > biggest_idx:
height = max(buliding[idx], height)
total += height
idx -= 1
print(total + buliding[biggest_idx])
리스트 슬라이싱에 문제가 있었나...
여튼 시작 지점, 끝 지점, 기둥이 되는 지점을 가지고도 문제를 풀 수 있었다.
