[백준][Java] 2304번 - 창고 다각형

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

---

풀이

1. 입력받은 기둥 x 좌표 순서로 정렬
2. 다각형을 y축과 평행하게 3등분으로 분할 (왼쪽, 오른쪽, 중간)
   중간은 다각형의 최대 높이인 부분으로 지정함
3. 왼쪽과 오른쪽의 넓이를 구함
4. 왼쪽과 오른쪽을 구하면서 자연스럽게 중간 부분의 양쪽(오른쪽, 왼쪽) 기둥을 구할 수 있음
5. 중간 부분 넓이까지 구하여 세 부분의 넓이를 더한 최종 넓이를 구함

다각형의 왼쪽과 오른쪽이 계단식으로 높다진다는 점을 생각하면 쉽게 풀 수 있는 문제이다. 처음에는 왼쪽과 오른쪽 두 개의 그룹으로 다각형을 나누어 구하는 방법으로 문제를 해결하려는 방식으로 잘못 접근해서 생각보다 시간이 걸렸다.

---

답

import java.io.*;
import java.util.StringTokenizer;
import java.lang.*;

class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int	N = Integer.parseInt(br.readLine());
		int arr[][] = new int[N][];
		
		int	max_h = 0;
		for (int i = 0; i < N; i++) {
			arr[i] = new int[2];
			StringTokenizer st = new StringTokenizer(br.readLine());
			arr[i][0] = Integer.parseInt(st.nextToken());
			arr[i][1] = Integer.parseInt(st.nextToken());
			if (max_h < arr[i][1])
				max_h = arr[i][1];
		}
		
		if (N == 1) {
			System.out.print(arr[0][1]);
			return;
		}
		
		int temp[];
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (arr[i][0] > arr[j][0]) {
					temp = arr[i];
					arr[i] = arr[j];
					arr[j] = temp;
				}
			}
		}
		
		int	totalArea = 0;
		int leftHigh = arr[0][1];
		int i = 0;
		while (i < N) {
			leftHigh = arr[i][1];
			if (leftHigh == max_h) {
				break;
			}
			while (leftHigh >= arr[i][1]) {
				totalArea += leftHigh * (arr[i + 1][0] - arr[i][0]);
				i++;
			}
		}
		
		int rightHigh = arr[N - 1][1];
		int j = N - 1;
		while (j > 0) {
			rightHigh = arr[j][1];
			if (rightHigh == max_h) {
				break;
			}
			while (rightHigh >= arr[j][1]) {
				totalArea += rightHigh * (- arr[j - 1][0] + arr[j][0]);
				j--;
			}
		}
		
		totalArea += max_h * (arr[j][0] - arr[i][0] + 1);

		System.out.print(totalArea);
	}
}