백준 - 2304번, 창고 다각형

[Silver II] 창고 다각형 - 2304

문제 링크

1. 문제 설명

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

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

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

그림1 . 기둥과 지붕(굵은 선)의 예

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

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

1.1 입력

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

1.2 출력

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

2. 풀이

2.1 요구사항 정리

1. 기둥 높이가 N개 주어진다. 지붕의 어떤 부분도 오목한 부분이 없게 만들어야 한다.
2. 주어지는 기둥 높이로 만들 수 있는 최소 크기의 창고를 구하라.

2.2 풀이 논리

한쪽 방향으로 기둥을 탐색하면서 더 큰 기둥이 나올 때까지 x 좌표를 저장해 지붕 높이를 지정하는 방법으로 구현할 수 있다. LIFO든 FIFO든 상관없이 담아뒀던 정보를 꺼낼 수 있는 자료구조를 사용한다. 아래에서 구현 논리를 세부적으로 이야기한다.

1. 왼쪽부터 오른쪽을 탐색하면서 더 큰 기둥이 나올 때까지 지붕 높이를 지금까지의 가장 큰 기둥 높이로 지정한다.
2. 기둥들 중간에 가장 높은 기둥이 있으면 오른쪽에 1번 연산이 이루어지지 않은 기둥이 남으므로 오른쪽부터 왼쪽으로 탐색하면서 같은 연산을 한다.
3. 만들어진 지붕대로 창고 넓이를 구한다.

2.3 코드

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[1001]; // 기둥 x 좌표를 인덱스로, 높이를 값으로 갖는 배열
        int start = Integer.MAX_VALUE; // 창고 중 가장 왼쪽 기둥의 x 좌표
        int end = 0; // 가장 오른쪽 x 좌표
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken()); // x 좌표
            int y = Integer.parseInt(st.nextToken()); // 높이
            arr[x] = y; // arr에 저장
            start = Math.min(start, x);
            end = Math.max(end, x);
        }

        Stack<Integer> stack = new Stack<>();
        // 왼쪽부터 오른쪽으로 탐색
        int loop = arr[start];
        for (int i = start + 1; i <= end; i++) {
            if (arr[i] < loop) { // 더 높은 기둥이 나올 때까지 현재 기둥 높이로 지붕 높이를 지정
                stack.push(i); // 하기 위해 스택에 저장
            }
            else { // 더 높은 기둥이 나오면
                while (!stack.isEmpty()) {
                    int x = stack.pop(); // 이전에 스택에 쌓인 x 좌표들의
                    arr[x] = loop; // 지붕 높이를 지정한다
                }
                loop = arr[i]; // loop 값 최신화
            }
        }
        stack.clear();

        //오른쪽에서 왼쪽으로 탐색
        loop = arr[end];
        for (int i = end - 1; i >= start; i--) {
            if (arr[i] < loop) stack.push(i);
            else {
                while (!stack.isEmpty()) {
                    int x = stack.pop();
                    arr[x] = loop;
                }
                loop = arr[i];
            }
        }

        int answer = 0;
        for (int i = start; i <= end; i++) {
            answer += arr[i];
        }

        System.out.print(answer);
    }
}