[백준/2304/파이썬] 창고 다각형

창고를 지어 봅시다. 

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

2304번: 창고 다각형

조건

N개의 막대기둥이 일렬로 세워져 있음. 기둥들의 폭은 모두 1M.

• 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결 되어야한다.
• 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야한다.
• 지붕의 가장자리는 땅에 닿아야한다.
• 지붕의 수직은 옆면에 닿아야함.
• 비가올때 물이 고이지 않도록, 오목하게 들어간 부분이 없어야함.

입력

1.1≤N≤1,000 ,

2.각 기둥의 왼쪽 면의 위치를 나타내는 정수 L,

3.높이를 나타내는 정수 H

가장 작은 다각형의 면적을 구해야한다.

SOL)

이 문제를 보고 처음든 생각은, 자료구조를 이용하라고 여기서 !? 뭘 어케 써야하지?!

일단, 예시 input을 보면서 , 조건에 맞춰 하나씩 해봄.

 

idea1

기둥이 가장 높은것 부터 배치를 해볼까 ? ⇒ 기둥을 높은것 부터 배치해서 사각형을 구성해볼까? Fail) 두번째의 기둥이 제일 높은 기둥 기준 왼쪽이냐 오른쪽이냐에 따라 계산을 다 다르게 해줘야하고, 또 , 3번째 기둥을 세울때 첫번째 높은 기둥 옆인지, 두번째 기둥옆인지 , 분기가 너무 많이 발생하게 된다.

 

idea 2

• 최고높이를 기준으로 , 왼쪽 / 오른쪽을 나눠서 생각
• 0~N까지의 모든 좌표에 , 해당 높이를 담는다는 생각으로 pillar(기둥) 생성.
• 더 큰값이 들어오면, 교체해주고, 그 값을 계속 더해주면됨. (너비는 1이니까 높이 == 넓이)
• 기둥을 1개,1개,1개 다 나눠서 이어붙인다는 느낌으로 생각하면 편함.

import sys
input = sys.stdin.readline

maxH=1
maxL=0
n= int(input())
pillar=[]

for i in range(n):
	L,H = map(int,input().strip().split())
	pillar.append([L,H])
	if maxL<L:
		maxL=L
	if maxH<H:
		maxH=H
		maxindex =L

pillarList=[0] *(maxL+1)

for l,h in pillar:
	pillarList[l]=h
total=0
temp=0

for i in range(maxindex+1):
    if pillarList[i]>temp:
        temp=pillarList[i]
    total+=temp
temp=0
for i in range(maxL,maxindex,-1):
    if pillarList[i] > temp:
        temp=pillarList[i]
    total+=temp
    
print(total)