백준 2304번: 창고 다각형

문제 설명

• 창고를 연결해야 합니다.
• 오목한 부분이 존재하면 안됩니다.
• 너비를 최소로 만들어야 합니다.

접근법

• 더 큰 기둥이 나올 때 이전까지의 너비를 더해주는 방법으로 접근했습니다.

• 테스트케이스에서는 발생하지 않지만 고려해야 할 상황이 존재합니다.
  * 가장 큰 기둥 ~ 마지막 기둥 사이에 마지막 기둥보다 더 큰 기둥이 나타나는 경우입니다.
  
  마지막 기둥 -> 가장 큰 기둥을 순회하면 이전과 똑같은 방식을 적용시킬 수 있습니다.
  

결론적으로 시작~가장 큰 기둥, 가장 큰 기둥~끝 두번의 계산이 필요합니다.

정답

import java.util.*;

class pos implements Comparable<pos> {
	int x;
	int y;
	int idx;
	public pos(int x, int y, int idx) {
		super();
		this.x = x;
		this.y = y;
		this.idx = idx;
	}
	
	@Override
	public int compareTo(pos o) {
		return this.x-o.x;
	}

	@Override
	public String toString() {
		return "pos [x=" + x + ", y=" + y + ", idx=" + idx + "]";
	}
	
	
	
}

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		List<pos> lst = new ArrayList<pos>();
		for (int i = 0; i < N; i++) {
			int x = sc.nextInt();
			int y = sc.nextInt();
			lst.add(new pos(x,y,i));	
		}
		
		Collections.sort(lst); // x값을 기준으로 정렬해 줍니다.

		// 입력순서로 넣었던 인덱스값을 정렬 후 순서로 바꿔줍니다.
		for (int i = 0; i < N; i++) {
			lst.get(i).idx = i;
		}
		
		
		pos compare = null;
		int answer = 0;
		for (int i = 0; i < N; i++) {
			if(compare == null) {
				compare = lst.get(i);
			}else {
				pos now = lst.get(i);
				// 더 큰 막대기가 등장하면 
				if(compare.y < now.y) {
					answer += compare.y*(now.x-compare.x); // 직전까지의 너비를 계산합니다.
					if(i == N-1) { // 해당 막대기가 마지막 막대기라면
						answer += now.y; // (이 코드는 `직전`까지의 너비를 계산하기 때문에) 해당 막대기의 길이만큼을 따로 더해줍니다.
						break;
					}else {
						compare = now; // 마지막 막대기가 아니라면 더 큰 막대기를 비교군으로 정해줍니다.
					}
				}
				if(i == N-1) { // 마지막 막대기가 비교막대기보다 낮은 경우입니다. // 이 경우 마지막~가장 큰 막대기 까지 거꾸로 비교하면서 너비를 더해줍니다.
					
					// '더 큰 막대기가 등장하면 직전까지의 너비를 더한다' 의 로직은 동일합니다.
					pos reverse_comp = null;
					for(int j = N-1;j>compare.idx;j--) { // 마지막 인덱스부터 가장 큰 막대기의 인댁스까지 거꾸로 순회합니다.
						if(reverse_comp == null) {
							reverse_comp = lst.get(j);
						}else {
							pos reverse_now = lst.get(j);
							if(reverse_comp.y<reverse_now.y) { // 나보다 더 큰 막대기가 등장한다면 갱신해 줍니다.
								answer += reverse_comp.y*(reverse_comp.x-reverse_now.x);
								reverse_comp = reverse_now;
							}
							if(j-1 == compare.idx) { // 가장 큰 막대기에 도달했다면
								answer += (reverse_comp.x-compare.x)*(Math.min(reverse_comp.y,compare.y));
							}
						}
					}
					answer += compare.y; // `직전`까지의 너비만 더하기 때문에 가장 큰 기둥의 너비는 더해지지 않았습니다. 여기서 가장 큰 기둥의 너비를 더해줍니다.
				}
			}
		}

		// 입력값이 하나인 경우를 예외처리합니다.
 		if(N == 1) {
			System.out.println(lst.get(0).y);
		}else {			
			System.out.println(answer);
		}		
	}

}