파이썬) 창고 다각형 - BOJ

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

2304번: 창고 다각형

 

n = int(input())

arr = [0 for _ in range(1001)]

mh = 0

height_idx = 0

for _ in range(n):
    idx, h = map(int, input().split())

    arr[idx] = h

    if mh < h:
        height_idx = idx
        mh = h
prev_h = 0
left_value = 0
for i in range(height_idx+1):
    # 왼쪽에서 가장 큰 기둥까지
    if arr[i] == 0:
        left_value += prev_h
    else:
        if prev_h < arr[i]:
            prev_h = arr[i]
            left_value += arr[i]
        else:
            left_value += prev_h
    # print(
    #     f'i = {i}, arr[i] = {arr[i]}, prev_h = {prev_h}, left_value = {left_value}')
# print(left_value)


right_value = 0
prev_h = 0

for i in range(len(arr)-1, height_idx, -1):
    # 오른쪽에서 가장 큰 기둥까지
    prev_h = max(arr[i], prev_h)
    right_value += prev_h
print(right_value + left_value)

# arr.append(list(map(int, input().split())))

이번 문제는 간단했지만 뭔가 많이 헷갈렸다.

우선 가장 큰 기둥을 기준으로 왼쪽 오른쪽으로 나누어

왼쪽은 현재값과 현재값 -1의 값을 비교해 왼쪽의 크기를 비교해나아간다.

오른쪽 또한 마찬가지로 진행했다.