[BOJ] 2304 창고 다각형

2304번: 창고 다각형 (acmicpc.net)

생각보다 간단하고, 간단하게 생각하면 쉽게 풀리는 문제였다.
문제는 요새 너무 어려운 문제들을 풀다보니 복잡하게 생각하는 습관이 들었나보다..

로직은 간단하다.

가장 높은 기둥을 찾고 그 기둥까지와 거리와 그 기둥의 높이를 곱해 면적을 누적한다.

제일 높은 기둥 파란색 부분을 누적


좌우로 그 다음 높은 기둥을 찾아서 해당 x좌표까지의 거리와 찾은 기둥의 높이를 곱해 면적을 구한다.

그다음 높은 기둥인 16,8까지의 넓이 누적
다음으로 높은 기둥까지의 넓이 누적

이런식으로 진행한다.

높은 기둥 순서대로 방문하기위해 Arrays.sort()메소드를 이용해서 배열을 기둥의 높이 순으로 내림차순으로 정렬했다.

package com.algo.boj;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BOJ2304PolyWarehouse {

	private static int index;

	public static void main(String[] args) throws Exception{

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int max = 0;
		index = 0;
		int[][] map = new  int[N][];
		for (int i = 0; i < N; i++) {
			StringTokenizer	st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			map[i]=new int[] {x,y};
			if( y > max) {
				index =x;
				max= y;
			}
		}//입력받는 for문
		Arrays.sort(map, (o1,o2) -> {
			if(o2[1]==o1[1]) return Math.abs(index - o2[0]);
			return o2[1]-o1[1];
		});
		int lindex = index;
		int rindex = index;
		int sum =0;
		for (int i = 1; i < map.length; i++) {
			if(map[i][0]> rindex ) {					//오른쪽 탐색
				sum += map[i][1] * (map[i][0] -rindex); //높이 차이곱하기 거리차이
				rindex = map[i][0];						//rindex업데이
			}else if(map[i][0] < lindex){ 				//왼쪽 탐색
				sum += map[i][1] *(lindex -map[i][0]);
				lindex = map[i][0];
			}
		}
		System.out.print(sum+max);
	}
}