N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.
그림1 . 기둥과 지붕(굵은 선)의 예
창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
n = int(input())
lst = []
result = 0
for i in range(n) :
a,b = map(int,input().split())
lst.append([a,b])
#기둥을 x축 순으로 정렬한다.
lst.sort()
#가장 높은 기둥의 번호를 알아낸다.
i = 0
for l in lst :
if l[1] >result :
result = l[1]
idx = i
i += 1
#초기 높이는 첫번째 기둥의 높이
height = lst[0][1]
#최대 높이전까지 돌면서 다음 기둥이 현재보다 높으면
#result에 현재의 면적을 계산해서 더해주고 높이를 다음 기둥으로 갱신한다.
for i in range(idx) :
if height < lst[i+1][1] :
result += height * (lst[i+1][0]-lst[i][0])
height = lst[i+1][1]
#아니면 그냥 현재면적을 더해준다.
else :
result += height * (lst[i+1][0] - lst[i][0])
#뒤에서부터도 똑같이 진행한다.
height = lst[-1][1]
for i in range(n-1, idx, -1) :
if height < lst[i-1][1] :
result += height * (lst[i][0]-lst[i-1][0])
height = lst[i-1][1]
else :
result += height * (lst[i][0] - lst[i-1][0])
print(result)
감사합니다