[백준] 2304 - 창고 다각형 (Python)

문제

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

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

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

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

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

---

입력

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

출력

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

---

입력 예시

7
2 4
11 4
15 8
4 6
5 3
8 10
13 6

출력 예시

98

---

해결 방법

 

아이디어 1. 완전 탐색으로 구하기

 

1부터 기둥의 최대 높이에 대해

현재 탐색중인 기둥의 높이보다 큰 가장 왼쪽 기둥과 가장 오른쪽 기둥의 위치를 구해서 두 기둥의 위치 차 + 1을 정답에 더해주는 방식으로 탐색해 나가면 창고의 넓이를 구할 수 있다. 

n = int(input())

columns = []

for _ in range(n):
    columns.append(tuple(map(int,input().split())))
columns.sort()

max_height = max([t[1] for t in columns])
answer = 0

for i in range(1, max_height+1):
    left = 0
    right = 0
    for j in range(n):
        # 기둥 높이가 i 이상인 가장 왼쪽 기둥 찾기
        column = columns[j]
        if column[1] >= i:
            left = column[0]
            break
    
    for k in range(n-1,-1,-1):
        column = columns[k]
        # 기둥 높이가 i 이상인 가장 오른쪽 기둥 찾기
        if column[1] >= i:
            right = column[0]
            break
    if right != 0:
        # 위에서 구한 위치를 바탕으로 높이 i에 해당하는 면적 구하기
        answer += (right-left+1)

print(answer)

 

아이디어2. 투 포인터로 접근하기

 

이 문제를 처음 봤을 때 창고의 높이가 높아지는 방향은 쉽게 생각 났지만, 창고의 방향이 낮아지는 쪽은 잘 생각이 나지 않았다. 

그래서 창고의 제일 왼쪽과 오른쪽에서 두번 접근하는 방법으로 구현하였다. 

 

왼쪽에서 접근할 때는 이번에 접근할 높이가 기존 높이보다 크거나 같으면 여태까지의 누적합을 통해 창고의 넓이를 갱신하고, 창고의 최대 높이 까지 반복되도록 하였다.

오른쪽에서 접근할 때는 "크거나 같다"에서 "같다"의 조건을 빼서 예를 들면 창고 높이의 최대 높이가 연속으로 3번 나와서 왼쪽과 오른쪽 접근에서 겹치는 부분을 제거하였다. 

n = int(input())

columns = []

for _ in range(n):
    columns.append(tuple(map(int,input().split())))
columns.sort()

max_height = max([t[1] for t in columns])

current = 0
index = 0
answer = 0

for column in columns:
    pos,height = column

    if current <= height:
        answer += (pos-index)*current
        current = height
        index = pos
        
columns.reverse()
current = 0
index = 0

for column in columns:
    pos,height = column
    
    if current < height:
        answer += (index-pos)*current
        current = height
        index = pos
    if height == max_height:
        current = height
        break

answer += current

print(answer)