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

 

문제

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

 

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

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

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

 

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

 

 

 

입력

 

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다.

 

그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

 

 

출력

 

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

 

 

 

풀이

 

이 문제는 기둥의 개수와 높이가 같더라도 기둥이 세워진 위치가 다르면 답이 달라 지기 때문에 몇 번째 위치에 기둥이 있는지 파악하는게 중요했다.

 

그래서 몇 번째 기둥이 있는지 파악하기 위해 정렬을 했고, 기둥의 높이 중 가장 큰 높이가 얼마인지 찾기 위해 max 함수를 사용했다.

 

그리고빗 물이 고이지 않는 지붕의 최소 넓이를 찾아야 하므로, 정렬된 기둥의 높이를 비교했다.

 

가장 큰 높이를 가진 기둥을 기준으로 왼쪽 기둥들의 경우 현재 기둥의 높이가 낮더라도 이전 기둥 중에서 더 높은 기둥이 있었다면 지붕의 높이는 이전 기둥의 최대 높이를 기준으로 만들어 진다.

 

마찬가지로 가장 큰 높이를 가진 기둥의 오른쪽 기둥들은 오른쪽에서 부터 큰 기둥이 있다면 지붕의 높이가 새로 갱신된다. 이후 가장 큰 높이를 가진 기둥들의 거리를 이용해 지붕의 넓이를 계산했다.

​

[풀이 요약]

1. 기둥들을 위치를 기준으로 정렬
2. 가장 높은 기둥을 찾고 왼쪽에 있는 가장 높은 기둥, 오른쪽에 있는 가장 높은 기둥의 위치를 파악
3. 가장 높은 기둥을 중심으로 왼쪽부터 가장 높은 기둥을 만날때 까지 지붕의 넓이 계산
4. 가장 높은 기둥을 중심으로 오른쪽에서부터 가장 높은 기둥을 만날때 까지 지붕의 넓이 계산
5. 1번에서 파악한 왼쪽에 있는 가장 높은 기둥, 오른쪽에 있는 가장 높은 기둥의 위치와 기둥의 높이를 곱해 지붕의 넓이를 계산
6. 3, 4, 5에서 구한 넓이를 더해서 출력

 

 

Code

 

 

import sys
input=sys.stdin.readline

lst=[]
N=int(input())
for i in range(N):
    lst.append(list(map(int,input().split()))) #0은 왼쪽벽 1은 높이
lst.sort()
high=max(lst, key= lambda x: x[1])
last_x=0
a=0
for i in range(N):
    if lst[i][1]==high[1]:
        last_x=lst[i][0]
        a=i
lst_l=lst[0:a+1]
lst_r=lst[a:]
lst_r.sort(reverse=True)
# high[1]=가장높은 높이
bef_h=0 # 현재까지 기둥들의 높이 중 가장 높은 기둥의 높이를 저장
bef_x=0 # 높이를 저장한 기둥의 위치가 어딘지 저장
sum_n=0 # 지붕넓이의 합
for i in lst_l:
    if i[1]>bef_h: # 현재 기둥이 이전에 기둥들 보다 높다면 새로 만들어질 지붕의 높이를 갱신하고 이전 지붕의 넓이를 계산한다.
        sum_n+=bef_h*(i[0]-bef_x)
        bef_h=i[1]
        bef_x=i[0]
        
bef_h=0
bef_x=0
for i in lst_r:
    if i[1]>bef_h:
        sum_n+=bef_h*(bef_x-i[0])
        bef_h=i[1]
        bef_x=i[0]
        
sum_n+=(lst[a][0]+1-high[0])*high[1]
print(sum_n)

 

---

 

 

 

가장 높은 기둥의 오른쪽 부분은 역순으로 계산하는게 가장 간단하고 쉽다.

 

 

2304번: 창고 다각형