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

📌 문제

알고리즘 분류 : 브루트포스 알고리즘
난이도 : 실버2
출처 : 백준 - 창고 다각형

🦧 문제 풀이 접근

브루트포스 알고리즘으로 문제를 해결한다.
객체 배열을 x좌표를 기준으로 정렬한다.
반복문을 통해 앞 좌표의 높이보다 높아졌을때 직사각형 만큼의 넓이를 더해준다.
해당과정을 뒤에서도 반복한다.

💻 code

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        Pos arr[] = new Pos[N];
        int highestPos=0, highestHeight = 0;
        for(int i=0;i<N;i++) {
            StringTokenizer st = new StringTokenizer(br.readLine()," ");
            int cPos = Integer.parseInt(st.nextToken());
            int cHeight = Integer.parseInt(st.nextToken());
            arr[i] = new Pos(cPos,cHeight);
            if(highestHeight<cHeight) {
                highestHeight = cHeight;
                highestPos = cPos;
            }
        }
        Arrays.sort(arr);
        int sum=0;
        int lastHeight=0;
        int lastPos=0;
        for(int i=0;i<N;i++) {
            if(i==0) {
                lastPos = arr[i].pos;
                lastHeight = arr[i].height;
            }
            else if(lastHeight<=arr[i].height) {
                sum+=(arr[i].pos-lastPos)*lastHeight;
                lastPos = arr[i].pos;
                lastHeight = arr[i].height;
            }
        }
        lastHeight=0;
        lastPos=0;
        for(int i=0;i<N;i++) {
            if(i==0) {
                lastPos = arr[N-1-i].pos;
                lastHeight = arr[N-1-i].height;
            }
            else if(lastHeight<arr[N-1-i].height) {
                sum+=(lastPos- arr[N-1-i].pos)*lastHeight;
                lastPos = arr[N-1-i].pos;
                lastHeight = arr[N-1-i].height;
            }
        }
        System.out.println(sum+highestHeight);
    }
}
class Pos implements Comparable<Pos>{
    int pos;
    int height;
    Pos(int pos, int height){
        this.pos = pos;
        this.height = height;
    }

    @Override
    public int compareTo(Pos o) {
        return this.pos - o.pos;
    }
}

🥇 결과

🎓 느낀점

어렵지 않은 브루트포스 문제다. 가장 높은 부분이 이어지는 경우 예외 처리를 잘 하자.