문제
N개의 기둥 위치와 높이가 주어질 때, 기둥을 감싸는 창고 다각형의 넓이를 구하라.
입력
첫째 줄에 N, 이후 N줄에 (위치, 높이)가 주어진다.
출력
창고 다각형의 넓이를 출력한다.
예제
| 입력 | 출력 |
|---|---|
7 2 4 11 4 15 8 4 6 5 3 8 10 13 6 | 98 |
풀이
가장 높은 기둥을 기준으로 왼쪽은 왼→오, 오른쪽은 오→왼으로 스위핑하며 넓이를 누적한다.
- 각 위치에 기둥 높이를 기록하고 최고 높이와 위치를 찾는다
- 왼쪽부터 최고 기둥까지 스위핑: 현재까지의 최대 높이를 넓이에 누적
- 오른쪽부터 최고 기둥까지 스위핑: 현재까지의 최대 높이를 넓이에 누적
- 최고 기둥 높이를 더한다
핵심 아이디어: 최고 기둥 기준 양쪽에서 접근하면 지붕선은 항상 비감소/비증가이다.
코드
package day499;
import java.io.*;
import java.util.*;
public class Day455BOJ2304창고다각형 {
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int[] roof = new int[1001];
int N = Integer.parseInt(br.readLine());
int idx = 0;
int max = 0;
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
int l = Integer.parseInt(st.nextToken());
int h = Integer.parseInt(st.nextToken());
if (max < h) {
max = h;
idx = l;
}
roof[l] = h;
}
int ans = max;
int cur = 0;
for (int i = 0; i < idx; i++) {
if (cur < roof[i])
cur = roof[i];
ans += cur;
}
cur = 0;
for (int i = 1000; i > idx; i--) {
if (cur < roof[i])
cur = roof[i];
ans += cur;
}
System.out.println(ans);
}
}복잡도
- 시간: O(L) - L은 위치 범위 (최대 1000)
- 공간: O(L)