[Baekjoon] BF - 2304 창고 다각형

문제

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

 

풀이

오목하게 들어간 부분이 없으려면, 루프탑 기준 왼쪽과 오른쪽으로 나누어 문제 풀이를 진행해야 합니다.

오른쪽 부분은 순서를 뒤집어서 문제를 풀어야 루프탑과 연결했을 때 오목한 부분이 없습니다.

 

루프탑 기준으로 왼쪽 부분과 오른쪽 부분으로 나눈 후 왼쪽 부분의 합 + 오른쪽 부분의 합 + 루프탑 사이의 합을 구하면 됩니다.

 

예시

7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

 

왼쪽 배열: (2, 4) (4, 6) (5, 3) (8, 10)

오른쪽 배열: (8,10) (11, 4) (13, 6) (15, 8)

→ 루프탑: (8, 10)

 

왼쪽 배열의 합: (4 - 2) * 2 + (5 - 4) * 6 + (8 - 5) * 6

오른쪽 배열의 합: (15 - 13) * 8 + (13 - 11) * 8 + (11 - 8) * 8

루프탑 사이의 합: 10

 

코드

import sys

n = int(sys.stdin.readline().rstrip())
position = []

for _ in range(n):
    x, y = map(int, sys.stdin.readline().rstrip().split())
    position.append((x, y))

position.sort(key=lambda x: x[0])

# 루프탑(가장 높은 기둥) 찾기 
roof_top = max(position, key=lambda x: x[1])
# 루프탑 후보
max_index = [i for i, value in enumerate(position) if value[1] == roof_top[1]]

# 루프탑 기준으로 왼편, 오른편
left_max_index, right_max_index = min(max_index), max(max_index)
left, right = position[:left_max_index + 1], position[right_max_index:][::-1]

# 왼편, 오른편 면적 계산
def calculate(array):
    if not array:
        return 0

    sum = 0
    max_value = array[0][1]

    for i in range(len(array) - 1):
        sum += max_value * abs(array[i + 1][0] - array[i][0])
        if array[i][1] < array[i + 1][1]:
            max_value = max(max_value, array[i + 1][1])

    # 기둥 배열 + 루프탑까지 면적 계산
    return sum


print(
    # 왼편 + 루프탑 사이 + 오른편
    calculate(left) + (position[right_max_index][0] - position[left_max_index][0] + 1) * roof_top[1] + calculate(right)
)