2304번: 창고 다각형 (acmicpc.net)
생각보다 간단하고, 간단하게 생각하면 쉽게 풀리는 문제였다.
문제는 요새 너무 어려운 문제들을 풀다보니 복잡하게 생각하는 습관이 들었나보다..
로직은 간단하다.
가장 높은 기둥을 찾고 그 기둥까지와 거리와 그 기둥의 높이를 곱해 면적을 누적한다.
좌우로 그 다음 높은 기둥을 찾아서 해당 x좌표까지의 거리와 찾은 기둥의 높이를 곱해 면적을 구한다.
이런식으로 진행한다.
높은 기둥 순서대로 방문하기위해 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); } }