(Python/파이썬) - 백준(BOJ) 2304번 : 창고 다각형

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

2304번: 창고 다각형

---

• 문제 : 

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

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

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

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

 

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

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

 

 

 

---

• 풀이 :

구현 문제였습니다.

 

문제 설명에 적힌 지붕을 세우는 조건만 보면 꽤나 어려워 보이지만 주어진 예시그럼을 보면 쉽게 이해할 수 있습니다.

 

문제 해결 아이디어는

 

가장 높은 기둥을 기준으로 하고 왼쪽과 오른쪽 그룹으로  나누어 현재 탐색중인 가장 높은 기둥의 높이를 누적한다. 

 

입니다.

 

풀이입니다.

 

1. 기둥을 입력받으며 가장 높은 기둥과 그 기둥의 인덱스를 저장힙니다. 이 때, 가장 높은 기둥이 여러개라면 아무 그것들 중 아무 인덱스나 상관 없습니다. 기준점으로 삼을 기둥 하나만 있으면 됩니다.

 

2.  가장 높은 기둥의 인덱스를 기준으로 왼쪽, 오른쪽으로 나누어 진행합니다. 현재 탐색중인 그룹의 가장 높은 기둥 높이인 curr 변수를 사용합니다.

 

3. 왼쪽 그룹은 왼쪽에서 오름차순으로, 오른쪽 그룹은 오른쪽에서 내림차순으로 탐색합니다. 이 때, curr(탐색 중인 기둥들 중 가장 높은 기둥)를 계속 max값으로 갱신하고, 그 때의 높이를 정답에 더해줍니다. 

 

 

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

예시로, 위와 같은 상황이라면 왼쪽 그룹은 8번 인덱스까지 탐색하며 0 + 0 + 4 + 4 + 6 + 6 + 6 + 6 + 10 = 42가 되고 오른쪽 그룹은 8 + 8 + 8 + 8 + 8 + 8 + 8 = 56이 됩니다. 따라서 정답은 98입니다.

 

---

• 소스코드 : 

import sys
input = sys.stdin.readline

m = 0
m_idx = 0
pli = [0 for _ in range(1001)] # 기둥
for _ in range(int(input())):
    L,H = map(int,input().split())
    pli[L] = H
    if m < H: # 가장 높은 기둥과 그 기둥의 인덱스를 찾음
        m_idx = L
        m = H
curr = 0
answer = 0
for i in range(m_idx+1): # 왼쪽 그룹
    curr = max(curr,pli[i])
    answer += curr
curr = 0
for i in range(1000,m_idx,-1): # 오른쪽 그룹
    curr = max(curr,pli[i])
    answer += curr
print(answer)