[Python] 백준 2304: 창고 다각형

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

2304번: 창고 다각형

ANS

N = int(input())
arr =[0] * 1001
area = 0
for _ in range(N):
    idx, h = map(int, input().split())
    arr[idx] = h
arr_first = arr[:arr.index(max(arr))+1]
maxV = max(arr_first)

for idx in range(arr_first.index(maxV)):
    if arr_first[idx] > arr_first[idx+1]:
        arr_first[idx+1] = arr_first[idx]
area += sum(arr_first)


arr_last = arr[arr.index(maxV)+1:]
while sum(arr_last) != 0:
    last_maxV = max(arr_last)
    for idx in range(arr_last.index(last_maxV)): #최대 높이까지
        arr_last[idx] = last_maxV
    area += sum(arr_last[:arr_last.index(max(arr_last))+1])
    arr_last = arr_last[arr_last.index(max(arr_last))+1:]
print(area)

🔑

최대 높이(arr의 max값)를 기준으로 전반부와 후반부를 나눠 구현하고자 했다. 전반부는 계속 증가하는 추세라는 점을 주의하여야 하고, 후반부는 꾸준히 감소해야 하나, 후반부에서 max값을 따로 찾아서 그 값 전까지는 후반부 max값보다 작아지면 안 된다는 것이 중요한 부분이다. 따라서 후반부  max값까지의 리스트를 만들어주고자 했다.(arr_last) while문을 이용해서 이 리스트의 sum값이 0이 될 때까지(sum값이 0이 되어야 리스트를 끝까지 본 것이다.) 계속해서 후반부의 max값을 구해주는 식으로 코드를 구현했다. 인덱스 지정 문제 때문에 잠깐 헤멘 부분이 있었지만 비교적 수월하게 풀린 문제.