[BOJ] 2304 - 창고 다각형 JAVA

www.acmicpc.net/problem/2304

2304번: 창고 다각형

문제

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

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

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

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

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

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

입력

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

출력

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

예제 입력 1

7

2 4

11 4

15 8

4 6

5 3

8 10

13 6

예제 출력 1

98

 

 

 

 

 

 

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Stack;
import java.util.StringTokenizer;

class Pillar implements Comparable<Pillar>{
    int left;
    int height;
    Pillar(int left, int height) {
        this.left = left;
        this.height = height;
    }
    @Override
    public int compareTo(Pillar o) {
        return this.left < o.left ? -1 : 1;
    }
}

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        Stack<Pillar> leftStk = new Stack<>();
        Stack<Pillar> rightStk = new Stack<>();
        ArrayList<Pillar> pillars = new ArrayList<>();

        int n = Integer.parseInt(br.readLine());
        for(int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int L = Integer.parseInt(st.nextToken());
            int H = Integer.parseInt(st.nextToken());
            pillars.add(new Pillar(L, H));
        }
        Collections.sort(pillars);  // 입력 순서 보장되지 않는다. 정렬 필요

        // 가운데의 가장 높은 기둥을 기준으로 left, right 스택 채운다. 단, 높이가 증가하는 기둥만 채운다
        int maxHeight = 0;
        int len = pillars.size();
        for(int i = 0; i < len; i++) {
            if(maxHeight < pillars.get(i).height) {
                maxHeight = pillars.get(i).height;
                leftStk.push(pillars.get(i));
            }
        }
        maxHeight = 0;
        for(int i = len - 1; i >= 0; i--) {
            if(maxHeight < pillars.get(i).height) {
                maxHeight = pillars.get(i).height;
                rightStk.push(pillars.get(i));
            }
        }

        int ans = (rightStk.peek().left - leftStk.peek().left + 1) * rightStk.peek().height;
        int beforeLeft = leftStk.pop().left;
        while(!leftStk.isEmpty()) {
            int left = leftStk.peek().left;
            int height = leftStk.peek().height;
            ans += (beforeLeft - left) * height;
            beforeLeft = left;
            leftStk.pop();
        }

        int beforeRight = rightStk.pop().left + 1;
        while(!rightStk.isEmpty()) {
            int right = rightStk.peek().left + 1;
            int height = rightStk.peek().height;
            ans += (right - beforeRight) * height;
            beforeRight = right;
            rightStk.pop();
        }

        System.out.println(ans);
    }
}

 

처음 봤을 때는 문제의 그림을 보고 이차원 배열을 탐색하는 그래프 문제라고 생각했다.

 

DFS, BFS 문제를 너무 많이 풀다 보니까 일단 무작정 그런 쪽으로 생각하게 되는 거 같다.

정말 대놓고 보이는 게 아닌 이상은 항상 어떤 어떤 알고리즘을 적용시키는 게 좋을지를 먼저 생각해보자.

 

스택으로 분류 되어있지만 딱히 스택일 필요는 없는 문제. 그냥 어레이리스트를 사용해도 된다.

 

창고다각형은 가장 높은 기둥을 가운데에 두고 그 양 옆으로 높이가 점점 내려가는 모양을 띄게 된다.

 

가장 높은 기둥을 중앙일 때,

왼쪽 부분에서는 높이가 점점 올라가는 기둥들만,

오른쪽 부분에서는 높이가 점점 내려가는 기둥들만 따로 모은다.

그 후 넓이를 계산해주면 된다.

 

주의할 점은, 가운데에 오는 가장 높은 기둥이 여러 개일 경우를 대비하여 이것도 따로 계산해줘야 한다는 것이다.

 

 

 

알고나면 굉장히 간단한 해법인데 생각해내기가 쉽지 않았다.