[python] 백준 2304 창고 다각형

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

2304번: 창고 다각형

 

문제 해결

• 새로운 유형X
• 오목하게 들어간 부분이 없다는 것에서 최고 높이의 기둥 좌표를 알아야한다.
• 가장 왼쪽에서 최고 높이 좌표까지, 가장 오른쪽에서 최고 높이 좌표까지 이웃한 기둥 사이의 영역의 넓이를 계산해준다.
• 높이가 올라가면 앞으로 넓이가 더 커질 것이므로 타겟 높이를 설정해서 높이가 올라가면 바꿔주고 아니면 유지시킨다.

 

 

CODE

import sys
input = sys.stdin.readline


def main():
    idx = 0
    answer = 0
    for i, l in enumerate(I):
        if l[1] > answer:
            answer = l[1]
            idx = i

    h = I[0][1]

    for i in range(idx):
        answer += h * (I[i + 1][0] - I[i][0])
        if h < I[i + 1][1]:
            h = I[i + 1][1]

    h = I[-1][1]
    for i in range(n - 1, idx, -1):
        answer += h * (I[i][0] - I[i - 1][0])
        if h < I[i - 1][1]:
            h = I[i - 1][1]
    return answer

if __name__ == "__main__":
    n = int(input())
    I = []
    for _ in range(n):
        L, H = map(int, input().split())
        I.append((L,H))
    I.sort(key = lambda x: x[0])
    answer = main()
    print(answer)