[BOJ] 창고 다각형 - 2304 (S2)

시간 제한	메모리 제한
2 초	128 MB

문제

N개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 창고를 만들 때, 창고의 지붕은 다음과 같은 규칙으로 만들어진다:

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 높이와 같아야 한다.
3. 지붕의 수직 부분은 옆면 쪽으로 있어야 한다.

이렇게 지붕을 만들면 창고 다각형이 만들어진다. 이 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 창고 다각형의 면적을 출력한다.

풀이

이 문제는 기둥들로 만들어지는 창고의 최소 면적을 구하는 문제이다. 핵심은 각 위치에서의 지붕 높이를 어떻게 결정하느냐이다.

접근 방법

창고 다각형을 만들 때, 지붕은 항상 기둥의 높이에 맞춰져야 하며 계단 형태를 이룬다. 이때 물이 고이지 않도록 하려면:

1. 가장 높은 기둥을 기준으로 좌우로 나누어 생각한다.
2. 왼쪽에서 오른쪽으로 진행하면서, 현재까지 본 기둥 중 가장 높은 기둥의 높이로 지붕을 유지한다.
3. 오른쪽에서 왼쪽으로 진행하면서, 현재까지 본 기둥 중 가장 높은 기둥의 높이로 지붕을 유지한다.
4. 가장 높은 기둥이 여러 개면 그 사이는 최고 높이로 채운다.

풀이 과정

1. 위치별로 기둥의 높이를 저장한다. (배열 크기를 1001로 설정)
2. 가장 높은 기둥의 높이와 가장 오른쪽 기둥의 위치를 찾는다.
3. 왼쪽에서 시작: 왼쪽부터 순회하며 최고 높이에 도달할 때까지 현재까지의 최대 높이로 면적을 더한다.
4. 오른쪽에서 시작: 오른쪽부터 순회하며 최고 높이에 도달할 때까지 현재까지의 최대 높이로 면적을 더한다.
5. 중간 영역(가장 높은 기둥들 사이)의 면적을 더한다.

이 방법을 사용하면 각 위치를 최대 한 번씩만 방문하므로 효율적이다.

코드

N = int(input())

max_h = 0
pillar_list = [0] * 1001

max_loc = 0
for _ in range(N):
    loc, h = map(int, input().split())
    max_h = max(max_h, h)
    max_loc = max(max_loc, loc)
    pillar_list[loc] = h

# 왼쪽에서 시작
i_l = -1
cur = 0
ans = 0
while cur < max_h:
    i_l += 1
    cur = max(cur, pillar_list[i_l])
    ans += cur

# 오른쪽에서 시작
i_r = max_loc + 1
cur = 0
while cur < max_h:
    i_r -= 1
    cur = max(cur, pillar_list[i_r])
    ans += cur

if i_r == i_l:
    ans -= max_h
else:
    ans += max_h * (i_r - i_l - 1)

print(ans)

코드 설명

초기화 및 입력 처리

• pillar_list[0] * 1001: 위치별 기둥 높이를 저장 (위치가 1~1000 범위)
• max_h: 가장 높은 기둥의 높이
• max_loc: 가장 오른쪽 기둥의 위치

왼쪽에서 오른쪽으로 탐색

while cur < max_h:
    i_l += 1
    cur = max(cur, pillar_list[i_l])
    ans += cur

• 현재까지 만난 기둥 중 최대 높이(cur)를 유지하면서 면적을 누적
• 최대 높이(max_h)에 도달하면 종료

오른쪽에서 왼쪽으로 탐색

while cur < max_h:
    i_r -= 1
    cur = max(cur, pillar_list[i_r])
    ans += cur

• 오른쪽 끝에서 시작하여 왼쪽으로 이동하며 동일한 방식으로 처리

중간 영역 처리

if i_r == i_l:
    ans -= max_h
else:
    ans += max_h * (i_r - i_l - 1)

• i_l과 i_r이 만나는 지점 처리
• 같은 위치면 중복 제거, 다르면 사이 영역을 최대 높이로 채움

시간 복잡도

• 입력 처리: O(N)
• 왼쪽/오른쪽 탐색: O(max_loc) ≤ O(1000)
• 전체 시간 복잡도: O(N + 1000) = O(N)

N ≤ 1000이므로 충분히 빠르게 해결할 수 있다.

주의 사항

1. 기둥의 위치가 순서대로 주어지지 않을 수 있으므로 위치 기반 배열을 사용한다.
2. 가장 높은 기둥이 여러 개 있을 수 있으므로 좌우에서 탐색하는 방식을 사용한다.
3. 중간 영역의 중복 계산을 주의해야 한다.

다른 접근 방법

스택을 활용한 방법도 가능하지만, 이 문제의 경우 양쪽에서 탐색하는 방법이 더 직관적이고 구현이 간단하다.