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

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

 

가장 높은 기둥을 기준으로 좌 우로 나눔

 

왼쪽

0부터 시작해서 가장 높은 기둥의 index까지

우선 height는 가장 첫 번째 기둥 높이로 초기화한다

 

결과값에 height*(다음 기둥 위치-현재 기둥 위치)를 더해서 면적을 업데이트한다

만약 현재 기둥보다 다음 기둥이 높은 경우에는 height값을 다음 기둥 높이로 업데이트한다

 

오른쪽은

이 과정을 끝에서부터 가장 높은 기둥의 index까지 역순으로 진행한다

height는 가장 마지막 기둥 높이로 초기화 한다

결과값에 height*(현재 기둥 위치-이전 기둥 위치)를 더한다

마찬가지로 현재까지 탐색한 기둥 중 가장 높은 기둥을 height에 업데이트 해야 한다

 

굿!

 

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

[백준] 2304_창고 다각형 python

이 분의 풀이를 참고했다!

 

n = int(input())

info=[]
result=0
for i in range(n):
    position, height = map(int,input().split())
    info.append([position, height])
info.sort()

i=0
for h in info:
    if h[1]>result:
        result=h[1]
        idx=i
    i+=1

height = info[0][1]

for i in range(idx):
    if height<info[i+1][1]:
        result+=height*(info[i+1][0]-info[i][0])
        height=info[i+1][1]
    else:
        result+=height*(info[i+1][0]-info[i][0])
height=info[-1][1]

for i in range(n-1, idx, -1):
    if height<info[i-1][1]:
        result+=height*(info[i][0]-info[i-1][0])
        height=info[i-1][1]
    else:
        result+=height*(info[i][0]-info[i-1][0])
print(result)