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

문제

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

풀이 방법

여러개의 기둥들이 있고, 그 위에 지붕을 만드는 문제이다. 
문제의 포인트는 오목한 부분이 없어야하는 것이다. 그래서 나는 가장 높은 기둥을 찾고, 그 전과 후를 따로 계산했다.
우선 기둥들의 정보를 저장하고 정렬할 때 필요한 compareTo 함수를 재정의 해줬다. 기둥들의 순서가 순차적으로 들어오지 않기 때문에 정렬을 사용했다.
가장 높은 기둥을 기준으로 
앞부분에서는 현재 기둥보다 더 높은 기둥이 올 때만 값을 더해주고
뒷부분은 끝에서부터 오면서 더 높은 기둥이 올 때만 값을 더해주는 식으로 구현했다.

제출 코드

import java.io.*;
import java.util.*;
 
public class BJ_2304_창고다각형  {
	static class Top implements Comparable<Top> {
		int p, h;
		public Top(int p, int h) {
			this.p = p;
			this.h = h;
		}
		@Override
		public int compareTo(Top o) {
			return p-o.p;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken()); // 기둥 개수
		
		Top[] tops = new Top[N]; //기둥들 정보 저장
		int maxH = 0, max= 0; 
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int p = Integer.parseInt(st.nextToken()); //기둥 위치 
			int h = Integer.parseInt(st.nextToken()); //기둥 높이 
			tops[i]= new Top(p,h);
		}
		Arrays.sort(tops);
		for (int i = 0; i <N; i++) { //가장 높은 위치 찾기
			if(maxH<tops[i].h) {
				maxH = tops[i].h;
				max = i; 
			}
		}
		//가장 높은 기둥을 기준으로 반큼씩 계산
		int height =0, move = 0, sum =0; ; 
		for (int i = 0; i <= max; i++) {
			if(height < tops[i].h) {
				sum+= (tops[i].p - tops[move].p) * height;
				height =tops[i].h;
				move =i;
			}
		}
		sum+=tops[max].h;
		//가장 높은 기둥 이후의 기둥들 면적 계산
		int idx=0;
		height=0; move = 0;
		for (int i =N-1; i >=max; i--) {
			if(height < tops[i].h) {
				sum+= (tops[move].p -tops[i].p) * height;
				height =tops[i].h;
				move =i;
				idx = i;
			}
		}
		sum+= (tops[idx].p - tops[max].p) * tops[idx].h;
		
		System.out.println(sum);
	}
 
}