백준 2304 <창고 다각형>

위의 그림을 보게 되면 어떻게 구해야 할지 감이 오는 문제.

 

앞에서부터 시작해서 점점 커지는 기둥만 넣고 반대로 뒤에서부터 시작해서 점점 커지는 기둥을 넣고 계산하면 끝!

 

문제 풀이

1. 기둥의 시작위치가 랜덤 하기 때문에 class를 하나 만들어서 시작 위치 순으로 정렬
2. 가작 작은 위치부터 시작해서 증가하면서 커지는 기둥만 ArrayList에 넣기 그림에서는 2
3. 반대로 가장 높은 위치에서 시작해서 감소하면서 커지는 기둥만 ArrayList에 넣기 그림에서는 15
4. Arraylist에서 이전값의 h에다가 사이의 값을 곱해서 더하기
5. 마지막으로 가장높은 위치 한번 더 더해주기

주의 사항!

이렇게 해주게 되면

이렇게 색칠한 부분이 들어가지 않는다. 처음부터 시작한 것이 6,8 이 끝이고 뒹서부터 시작한 것이 8,8 이기 때문이다.

 

그러므로 (뒤에서 계산한 끝의 위치)- (처음부터 계산한 끝의 위치)*최대 높이 를 더해줘야 한다.

 

전체 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main{

	public static class cols implements Comparable<cols>{
		int x;
		int h;
		public cols(int x, int h) {
			super();
			this.x = x;
			this.h = h;
		}
		@Override
		public int compareTo(cols o) {
			// TODO Auto-generated method stub
			return this.x-o.x;
		}
		
	}
	static int n;
	static ArrayList<cols> divr,divl,num;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		n = Integer.parseInt(br.readLine());
		num=new ArrayList<cols>();
		divr=new ArrayList<cols>();
		divl=new ArrayList<cols>();
		for(int i=0;i<n;i++) {
			StringTokenizer st=new StringTokenizer(br.readLine());
			num.add(new cols(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken())));
		}
		Collections.sort(num);
		for(int i=0;i<n;i++) {
			if(divr.isEmpty()||divr.get(divr.size()-1).h<num.get(i).h) {
				divr.add(num.get(i));
			}
		}
		for(int i=n-1;i>=0;i--) {
			if(divl.isEmpty()||divl.get(divl.size()-1).h<num.get(i).h) {
				divl.add(num.get(i));
			}
		}
		int result=0;
		for(int i=1;i<divr.size();i++) {
			result+=(divr.get(i).x-divr.get(i-1).x)*divr.get(i-1).h;
		}
		for(int i=1;i<divl.size();i++) {
			result+=(divl.get(i-1).x-divl.get(i).x)*divl.get(i-1).h;
		}
		result+=(divl.get(divl.size()-1).x-divr.get(divr.size()-1).x)*divr.get(divr.size()-1).h;
		result+=divr.get(divr.size()-1).h;
		System.out.println(result);
	}

}