[BOJ] 창고 다각형

---

코드

import sys
# from collections import deque
input = sys.stdin.readline

# input
N = int(input())
pillars = []
for _ in range(N):
    pillars.append(list(map(int, input().split())))

# solution
pillars_sorted = sorted(pillars, key=lambda x: x[1], reverse=True)

tallest_pos = pillars_sorted[0][0]        # 가장 높은 기둥의 위치
tallest_height = pillars_sorted[0][1]    # 가장 높은 기둥의 높이
cur_l, cur_r = tallest_pos, tallest_pos    # 가장 높은 기둥 기준으로 왼쪽, 오른쪽에 마지막으로 놓은 기둥의 위치

ans = tallest_height    # 가장 높은 기둥의 넓이는 미리 더해둠

for i in range(1, N):
    pos = pillars_sorted[i][0]
    height = pillars_sorted[i][1]
    if pos < tallest_pos and pos < cur_l:
        ans += (height * (cur_l - pos))
        cur_l = pos
    elif pos > tallest_pos and pos > cur_r:
        ans += (height * (pos - cur_r))
        cur_r = pos
    
print(ans)

결과

풀이 방법

• 핵심은 가장 큰 기둥을 기준으로 양쪽 기둥들 중 일부를 선택하는데, 결과적으로 산 모양이 나오도록 선택해야 한다는 것이다.
• 그래서 우선 기둥들의 (위치, 높이)를 담은 리스트를 높이가 가장 큰 순서대로 정렬하였다.
• 정렬된 리스트를 순서대로 탐색하면서, 기둥을 선택했을 때 기준(가장 높은 기둥)의 왼쪽과 오른쪽으로 각각 갈수록 높이가 점점 낮아지는 것만 고른다
• 리스트가 이미 정렬되어 있기 때문에 탐색하는 기둥의 높이는 항상 이전 기둥보다 낮으므로 위치만 신경쓰면 된다
• 가장 높은 기둥을 기준으로 왼쪽, 오른쪽에 각각 마지막으로 놓은 기둥의 위치를 cur_l, cur_r 변수에 기록한다. 초기값은 기준 기둥의 위치이다.
• 현재 탐색하는 기둥의 위치가 기준보다 왼쪽(오른쪽)이고, 기준 왼쪽(오른쪽)으로 가장 멀리 있는 기둥의 위치보다 더 왼쪽(오른쪽)이라면 천장을 덮을 수 있다.
• 해당 기둥에 천장을 만들면 기둥높이 * |가장 가까운 기둥과의 거리| 만큼의 넓이를 더하여 가며 답을 구했다.

---