[백준 2304] 창고 다각형

문제

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

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

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

 

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

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

 

입력

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

 

출력

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

---

접근

처음에는 스택을 활용하여 현재 스택의 top보다 큰 크기가 나왔을 때 이전까지의 넓이를 구하도록 하였지만 예제로 나와있는 테스트 케이스만 통과하는 코드였다.

 

다른 사람들의 풀이를 보고 참고를 하였고 다음과 같은 과정으로 해결할 수 있었다.

- 현재 스택의 top에 있는 높이를 계속 더해준다.

- top과 비교하여 더 큰 높이가 나오면 pop을 해주고 더 큰 높이를 push한다.

- 이것은 위의 그림에서 모든 너비를 보라색의 사각형으로 채우는 과정을 거치게된다.

 

구현

N을 입력받은 후에 N개의 사각형 정보를 입력받는다.

이때 0으로 초기화된 wall_list에 바로 정보를 입력하고 최대높이와 최대높이의 위치를 찾아준다.

또한 마지막 인덱스를 찾아준다.

왜냐하면 최대높이를 기준으로 왼쪽에서 최대높이로, 오른쪽 끝에서 최대높이로 이동하면서 넓이를 구할 것이기 때문이다.

for _ in range(N):
    idx, h = map(int, input().split())
    wall_list[idx] = h
    if max_h < h:
        max_h = h
        max_h_idx = idx
    end_idx = max(end_idx, idx)

 

왼쪽에서 최대높이까지 탐색을 하면서 스택의 top을 계속 더해준다.

이때 스택의 top보다 현재 높이가 크다면 pop을 하고 현재 높이를 push하도록 한다.

stack = []
for i in range(0, max_h_idx+1):
    if not stack:
        stack.append(wall_list[i])
        answer += stack[-1]
    else:
        if stack[-1] < wall_list[i]:
            stack.pop()
            stack.append(wall_list[i])
        answer += stack[-1]

 

이제 오른쪽 끝에서 최대높이까지 탐색하면서 스택의 top을 계속 넓이에 더해준다.

stack = []
for i in range(end_idx, max_h_idx, -1):
    if not stack:
        stack.append(wall_list[i])
        answer += stack[-1]
    else:
        if stack[-1] < wall_list[i]:
            stack.pop()
            stack.append(wall_list[i])
        answer += stack[-1]

---

전체 코드

N = int(input())
wall_list = [0] * 1001
max_h = 0
max_h_idx = 0
end_idx = 0
for _ in range(N):
    idx, h = map(int, input().split())
    wall_list[idx] = h
    if max_h < h:
        max_h = h
        max_h_idx = idx
    end_idx = max(end_idx, idx)

answer = 0
stack = []
for i in range(0, max_h_idx+1):
    if not stack:
        stack.append(wall_list[i])
        answer += stack[-1]
    else:
        if stack[-1] < wall_list[i]:
            stack.pop()
            stack.append(wall_list[i])
        answer += stack[-1]

stack = []
for i in range(end_idx, max_h_idx, -1):
    if not stack:
        stack.append(wall_list[i])
        answer += stack[-1]
    else:
        if stack[-1] < wall_list[i]:
            stack.pop()
            stack.append(wall_list[i])
        answer += stack[-1]

print(answer)