[백준 2304] - 창고 다각형(JAVA)

[문제]

https://www.acmicpc.net/problem/2304

2304번: 창고 다각형

---

 

[문제풀이 전]

 

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하면 되는 문제입니다. 힌트에서는 문제 분류가 브루트포스로 되어있지만 x축 (기둥의 왼쪽 면의 위치) 기준으로 정렬을 하여 구하여 항상 작은 면적이 나오게 구현을 했기 때문에 그리디 방법이 아닌가 생각이 들기도 합니다.

브루트포스는 가능한 모든 경우의 수를 탐색하는데 그런 경우를 따져 풀지 않았다고 생각합니다. 혹시 제가 잘못된 생각을 했다면 댓글 남겨주시면 정말 감사하겠습니다 ㅎㅎ....

 

 

 

---

[문제풀이]

 

이 문제를 찾아오게 된다면 아마 한 방향으로 면적을 구하려다 실패를 해서이기 때문이지 않을까 생각을 합니다.

해당 문제는 제일 높은 기둥을 기준으로 문제의 조건에 맞게 오른쪽은 작아지는 구간만을 계산을 하고, 왼쪽 면적은 기둥이 커지는 구간만 계산을 한 뒤에 제일 큰 기둥의 면적을 더해주면 답이 구해집니다. 

 

 

---

 

[소스코드]

 

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

public class Main {

    static class LowHigh{
        int low;
        int high;

        public LowHigh(int low, int high) {
            this.low = low;
            this.high = high;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        ArrayList<LowHigh> list = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int l = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

            list.add(new LowHigh(l, h));
        }

        Collections.sort(list, (o1, o2) -> o1.low - o2.low); //x축 기준 정렬

        int sum = 0;
        int maxHeightPoint = 0;

        LowHigh highCol = list.get(0);
        for (int i = 1; i < list.size(); i++) {
            LowHigh currentCol = list.get(i);

            if (highCol.high <= currentCol.high) {
                sum += (currentCol.low - highCol.low) * highCol.high;
                highCol = currentCol;
                maxHeightPoint = i;
            }
        }


        highCol = list.get(list.size() - 1);
        for (int i = 1; i < list.size() - maxHeightPoint; i++) {
            LowHigh currentCol = list.get(list.size() - 1 - i);

            if (highCol.high <= currentCol.high) {
                sum += (highCol.low - currentCol.low) * highCol.high;
                highCol = currentCol;
            }
        }

        sum += list.get(maxHeightPoint).high;

        System.out.println(sum);
    }
}