[백준] 2304 창고 다각형 - python

문제 링크

이번 문제는 가장 작은 창고 다각형의 넓이를 구하는 문제였다.

이 문제는 가장 최고점을 기준으로 왼쪽은 계속 올라가고, 오른쪽은 계속 내려가는 다각형의 넓이를 구해서 풀어야 한다.

나는 최고점의 x위치를 찾고 이를 슬라이싱하여 풀었다.

# 창고 다각형

import sys
import copy

n = int(sys.stdin.readline().rstrip())

graph = []

for i in range(n):
    x, y = map(int, sys.stdin.readline().rstrip().split(' '))
    graph.append([x,y])

igraph = copy.deepcopy(graph)

graph.sort(key=lambda x : x[0])
igraph.sort(key=lambda x : -x[1])

x = graph.index(igraph[0])
left = graph[:x+1]
right = graph[x:]

result = graph[x][1]
px = left[0][0]
py = 0
for i in left:
    if py <= i[1]:
        result += py * (i[0] - px)
        px = i[0]
        py = i[1]
    else:
        result += py * (i[0] - px)
        px = i[0]

px = right[-1][0]
py = 0
for i in right[::-1]:
    if py <= i[1]:
        result += py * (px - i[0])
        px = i[0]
        py = i[1]
    else:
        result += py * (px - i[0])
        px = i[0]

print(result)

최고점을 기준으로 왼쪽, 오른쪽 리스트로 자르고, 이전 높이 보다 크다면 현재 높이를 저장하고, x의 길이를 구하여 직사각형 넓이를 더한다.
이런 식으로 구하면 최고점 넓이를 고려하는 부분이 빠지기 때문에 result의 초기값을 최고점 높이로 해주었다.

right 부분을 reverse 하여 계산했기 때문에 left와 계산은 같았다.