[BOJ] 2304 창고 다각형 바로가기
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
그림1 . 기둥과 지붕(굵은 선)의 예창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
✍ 코드
from collections import deque
from sys import stdin
M = [0, 0]
Array = []
sum = 0
N = int(stdin.readline())
for _ in range(N):
tmp = list(map(int,stdin.readline().split()))
Array.append(tmp)
if tmp[1] > M[1]: # 가장 큰 막대 기둥 찾기
M = tmp
Array.sort() # 기둥 위치 순으로 정렬
start = Array[0][0] # 시작 기둥 위치
middle = M[0] # 가장 큰 막대 기둥 위치
end = Array[-1][0] # 마지막 기둥 위치
Array = deque(Array)
cur = 0
for i in range(start,middle+1): # 시작 기둥 ~ 제일 큰 기둥
if Array[0][0] == i:
tmp = Array.popleft()
if tmp[1] > cur:
cur = tmp[1]
sum += cur
cur = 0
for i in range(end,middle,-1): # 마지막 기둥 ~ 제일 큰 기둥
if Array and Array[-1][0] == i:
tmp = Array.pop()
if tmp[1] > cur:
cur = tmp[1]
sum += cur
print(sum)