🥈 2304 창고 다각형
문제
N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.
- 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
- 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
- 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
- 지붕의 가장자리는 땅에 닿아야 한다.
- 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.
기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.
입력
첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다.
- N은 1 이상 1,000 이하
그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다.
- L과 H는 둘 다 1 이상 1,000 이하
출력
첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.
분석
문제 설명보다 그림과 예제를 보면서 이해한 문제이다..스택으로 분류되어 스택으로 풀어보려고 했으나 그럴 필요는 없었던 문제였다.
먼저 주어진 범위내에서 가장 높은 부분의 좌표를 저장해두고 이를 기준으로 왼쪽, 오른쪽을 나누어 탐색한다. 그리고 기존 최대 높이 값을 저장하는 before 변수를 두고 현재 위치 x의 높이와 비교해 더 높은 y값이 들어오면 갱신, 아니라면 기존 before 값으로 size값을 더해준다.
소스 코드
import sys
input = sys.stdin.readline
axis_X = [0 for _ in range(1001)] # X 축
max_x = max_y = 0 # 가장 높은 곳의 좌표
start_x, end_x = 1001, 0 # 시작 지점과 끝 지점
for i in range(int(input()):
x, y = map(int, input().split())
axis_X[x] = y
if max_y < y:
max_x, max_y = x, y
end_x = max(end_x, x)
start_x = min(start_x, x)
before = size = axis_X[start_x]
for here in range(start_x + 1, max_x + 1):
before = max(before, axis_X[here])
size += before
# 끝이 최대 높이가 되면 한 번 더하는 셈이되므로 같을 경우 제외함
if end_x != max_x:
before = axis_X[end_x]
size += before
for here in range(end_x - 1, max_x, -1):
before = max(before, axis_X[here])
size += before
print(size)