백준 #2304 - [S2] 창고 다각형 : 구현

(python3)

2304번: 창고 다각형

 

양쪽에서 접근하기

계단식으로 기둥 주변을 꽉꽉 채워주면 되는데요, 가장 높은 기둥을 기준으로 앞, 뒤를 나눠서 생각해야합니다. 앞부분은 직관적으로 이해하기가 쉽습니다. 쭉 탐색하면서 지금까지 높이중 가장 높았던 높이를 유지하면 됩니다. 문제는 꼭대기를 찍고 다시 내려가는 부분이죠.

이것도 정방향으로 해결하려면 지금 기둥부터 앞으로 나올 기둥들 중 가장 높은걸 채택해야합니다. 미래를 예측할순 없죠. 그래서 뒷부분은 뒤에서부터 탐색해주면 앞부분과 동일하게 해결이 가능해집니다.

가장 높은 기둥이 여러개라면? 가장 높은 첫기둥~가장 높은 마지막 기둥까지의 지붕은 직선으로 연결되어야합니다.

 

코드

import sys
from collections import deque
def solution(input) :
    N = int(input().strip())
    MAP = [0]*1001

    maxn = 0 # 첫 기둥 위치
    minn = 10000 #  마지막 기둥 위치
    

    for _ in range(N) : # 첫기둥, 마지막기둥 위치 찾으면서 기둥맵 완성
        n,l = list(map(int,input().split()))
        maxn = max(maxn,n)
        minn = min(minn,n)
        MAP[n] = l

    maxh = max(MAP) # 최고높이
    maxhs = [] # 최고높이 기둥들의 위치
    for i in range(minn, maxn+1) : # 최고 높이 기둥들 위치 찾기
        if MAP[i] == maxh :
            maxhs.append(i)
    
    mintopn = min(maxhs) # 최고 높이 기둥들 중 첫번째
    maxtopn = max(maxhs) # 최고 높이 기둥들 중 마지막

    minarea = 0
    t = 0
    for i in range(minn, mintopn) : # 최고 높이 기둥 전까지 계단식으로 올라가기
        t = max(t,MAP[i])
        minarea+=t

    minarea+=(maxtopn-mintopn+1)*maxh # 최고 높이 기둥 시작 ~ 끝까지는 직사각형

    t = 0
    for i in range(maxn,maxtopn,-1) : # 마지막 최고높이 기둥까지 뒤에서부터 계단식으로 올라가기
        t = max(t,MAP[i])
        minarea+=t

    print(minarea)

input = sys.stdin.readline
solution(input)

 

my solved.ac :

solved.ac