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

Condition

• TL : 2s
• 1<=n<=1000, 1<=L,H<=1000
• 기둥들의 위치와 높이가 주어진다
• 땅과 몇 개의 기둥 윗면을 연결해서 창고를 만든다
  • 오목하게 들어간 부분이 없어야 한다

Question

• 기둥들로 만들 수 있는 창고의 최소 면적을 구하라

Approach

• 분류 : 스택
• 스택
  • reference : https://velog.io/@holawan/%EB%B0%B1%EC%A4%80-2304%EC%B0%BD%EA%B3%A0-%EB%8B%A4%EA%B0%81%ED%98%95-python
  • 위치 순으로 기둥을 정렬한 후, 가장 높은 기둥을 선택
  • 첫 번째 기둥부터, 첫 번째 기둥을 기준으로 가장 높은 기둥 전까지 면적을 계속 더함
    • 기준 >= 다음 기둥 높이 : 기준을 더함
    • 기준 < 다음 기둥 높이 : 기준 높이를 더하고, 기준을 다음 기둥 높이로 갱신
  • 반대쪽에서도 똑같이 진행한다

Code

from sys import stdin
input = stdin.readline



def input_data():
    n = int(input())
    pillar_list = [tuple(map(int,input().split())) for _ in range(n)]
    pillar_list.sort()

    # 제일 높은 기둥 위치를 찾는다
    max_h = 0
    for i in range(n):
        h = pillar_list[i][1]
        if h > max_h:
            max_idx = i
            max_h = h
    return n, pillar_list, max_idx



def solution(n, pillar_list, max_idx):
    area = 0

    # 첫 번째부터 시작
    cl, standard = pillar_list[0]
    i = 0
    while i < max_idx:
        nl, nh = pillar_list[i+1]
        if standard >= nh:
            area += (nl-cl) *standard
        else:
            area += (nl-cl) *standard
            standard = nh
        i +=1
        cl = pillar_list[i][0]

    # 끝에서 시작
    cl, standard = pillar_list[n-1]
    i = n-1
    while i > max_idx:
        nl, nh = pillar_list[i-1]
        if standard >= nh:
            area += (cl-nl) *standard
        else:
            area += (cl-nl) *standard
            standard = nh
        i -=1
        cl = pillar_list[i][0]

    # 가장 높은 기둥 더하기
    area += pillar_list[max_idx][1]

    # 정답 return
    return area



print(solution(*input_data()))