[백준] 2304 창고 다각형 - 구현 + 그리디 JAVA

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

코드설명

구현 문제입니다.

 

문제의 해결방안 중 가장 중요한 아이디어는, 

각 좌표들이 있을때 문제에서 주어지는 가로 좌표의 위치를 직사각형의 우측하단 꼭지점이라고 생각하고 풀었습니다.

그렇게 생각을한다면, 각 직사각형의 높이가 커지는 지점에서 쉽게 높이를 구할 수 있습니다.

 

문제의 조건울 보면,

1. 지붕은 수평 부분과 수직 부분으로 구성되며, 모두 연결되어야 한다.
2. 지붕의 수평 부분은 반드시 어떤 기둥의 윗면과 닿아야 한다.
3. 지붕의 수직 부분은 반드시 어떤 기둥의 옆면과 닿아야 한다.
4. 지붕의 가장자리는 땅에 닿아야 한다.
5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.

라는 조건이 있는데, 이 조건을 통해 직사각형의 오목하게 들어간 부분이 없으므로 높이가 커지는 지점에서 항상 넓이를 구해야한다는 점을 알 수 있습니다.

 

가장 긴 기둥의 Index와 높이값을 찾아서 각 좌,우에서 넓이를 구해가는것이 주 로직입니다.

 

문제의 이해를 하는 중에서 헷갈리는점은, 기둥의 width 가 1개라는 조건이 없어서 문제에 대한 이해가 더 어려웠던 것 같습니다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;


public class Main {
	public static int N, maxWidthArrIndex = 0, maxHeight = 0;
	public static ArrayList<Node> arr = new ArrayList<>();
	public static int answer = 0;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine());
    	N = Integer.parseInt(st.nextToken());
    	
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine());
    		int a = Integer.parseInt(st.nextToken());
    		int b = Integer.parseInt(st.nextToken());
    		//최대값 갱신
    		if(maxHeight < b) {
    			maxHeight = b;
    		}
    		arr.add(new Node(a, b));
    	}
    	
    	//좌표 순으로 정렬
    	Collections.sort(arr);
    	
    	//반드시 좌표순으로 정렬후 최대값의 width 값 갱신
    	for(int i=0;i<N;i++) {
    		if(maxHeight == arr.get(i).height) {
    			maxWidthArrIndex = i;
    		}
    	}
    	
    	for(int i=0;i<maxWidthArrIndex;i++) {
    		for(int j=i+1; j<=maxWidthArrIndex;j++) {
    			//만약 현재 height보다 크다면, 넓이값을 저장해야 합니다.
    			if(arr.get(i).height <= arr.get(j).height) { //가장 높은층이 여러개일 수 있습니다.
    				answer += (arr.get(j).width - arr.get(i).width) * arr.get(i).height;
    				i = j; //기준을 이동 시킵니다.
    			}
    		}
    	}
    	
    	for(int i=N-1; i>maxWidthArrIndex; i--) {
    		for(int j=i-1; j>=maxWidthArrIndex; j--) { 
    			//만약 현재 height보다 크다면, 넓이 값을 저장해야합니다.
    			if(arr.get(i).height <= arr.get(j).height) { //가장 높은층이 여러개일 수 있습니다.
    				answer += (arr.get(i).width - arr.get(j).width) * arr.get(i).height;
    				i = j; //기준을 이동 시킵니다.
    			}
    		}
    	}
    	
    	System.out.println(answer + maxHeight);
    	
    }
    
}

class Node implements Comparable<Node>{
	int width;
	int height;
	public Node(int width, int height) {
		this.width = width;
		this.height = height;
	}
	
	@Override
	public int compareTo(Node other) {
		if(this.width > other.width) {
			return 1;
		}else if(this.width == other.width){
			return 0;
		}else {
			return -1;
		}
	}
	
}