백준 - 2304번(창고 다각형)

문제 출처: https://www.acmicpc.net/problem/2304

---

문제

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

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

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

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

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

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

---

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    private static class Pole implements Comparable<Pole> {

        int x;
        int y;

        public Pole(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pole o) {
            return this.x - o.x;
        }

    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(reader.readLine()); // 기둥의 개수

        List<Pole> poleList = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int x = Integer.parseInt(tokenizer.nextToken());
            int y = Integer.parseInt(tokenizer.nextToken());
            poleList.add(new Pole(x, y));
        }

        Collections.sort(poleList);

        int maxY = 0; // 가장 높은 기둥
        int index = 0; // 가장 높은 기둥의 인덱스

        // 가장 높은 기둥 찾기
        for (int i = 0, size = poleList.size(); i < size; i++) {
            if (poleList.get(i).y > maxY) {
                maxY = poleList.get(i).y;
                index = i;
            }
        }

        int area = 0; // 넓이를 저장하는 변수

        int leftY = poleList.get(0).y; // 왼쪽 끝 기둥
        int leftX = poleList.get(0).x; // x 좌표 위치

        for (int i = 1; i <= index; i++) {
            if (leftY <= poleList.get(i).y) {
                area += leftY * (poleList.get(i).x - leftX);
                leftY = poleList.get(i).y;
                leftX = poleList.get(i).x;
            }
        }

        int rightY = poleList.get(poleList.size() - 1).y; // 오른쪽 끝 기둥
        int rightX = poleList.get(poleList.size() - 1).x; // x 좌표 위치

        for (int i = poleList.size() - 2; i >= index; i--) {
            if (rightY <= poleList.get(i).y) {
                area += rightY * (rightX - poleList.get(i).x);
                rightY = poleList.get(i).y;
                rightX = poleList.get(i).x;
            }
        }

        area += maxY;

        System.out.println(area);
    }

}

---

• 각 기둥의 x 좌표와 높이 정보를 저장하는 클래스를 만든다.
• 각 기둥의 정보들을 저장하는 리스트를 생성하고, 리스트를 x 좌표를 기준으로 정렬한다.
• 가장 높은 기둥의 정보를 구한다. 이 기둥이 지붕의 좌, 우 구분점이 된다.
• 가장 높은 기둥을 구했으면 왼쪽부터 그 기둥까지의 넓이를 구하고, 그 다음 오른쪽에서 기둥까지의 넓이를 구한 뒤 둘을 합하고, 나머지 남은 최대 기둥 높이를 더하여 최종 넓이를 완성한다.
• 왼쪽과 오른쪽 지붕 탐색을 할 때 <= 연산을 사용하여 같은 높이의 기둥이 오는 경우도 처리하였다.