백준 2304번-창고 다각형(JAVA)

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

2304번: 창고 다각형

 

문제

N 개의 막대 기둥이 일렬로 세워져 있다. 기둥들의 폭은 모두 1 m이며 높이는 다를 수 있다. 이 기둥들을 이용하여 양철로 된 창고를 제작하려고 한다. 창고에는 모든 기둥이 들어간다. 이 창고의 지붕을 다음과 같이 만든다.

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

그림 1은 창고를 옆에서 본 모습을 그린 것이다. 이 그림에서 굵은 선으로 표시된 부분이 지붕에 해당되고, 지붕과 땅으로 둘러싸인 다각형이 창고를 옆에서 본 모습이다. 이 다각형을 창고 다각형이라고 하자.

그림1 . 기둥과 지붕(굵은 선)의 예

창고 주인은 창고 다각형의 면적이 가장 작은 창고를 만들기를 원한다. 그림 1에서 창고 다각형의 면적은 98 ㎡이고, 이 경우가 가장 작은 창고 다각형이다.

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

입력

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의 빈 칸을 사이에 두고 주어진다. L과 H는 둘 다 1 이상 1,000 이하이다.

출력

첫 줄에 창고 다각형의 면적을 나타내는 정수를 출력한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class BJ_02304 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		int TC = Integer.parseInt(br.readLine());
		int result = 0;
		int[][] polls = new int[TC][2];
		int tallest = Integer.MIN_VALUE;
		for (int t = 0; t < TC; t++) {
			st = new StringTokenizer(br.readLine(), " ");
			polls[t][0] = Integer.parseInt(st.nextToken());
			polls[t][1] = Integer.parseInt(st.nextToken());
		}
		// 기둥을 x 좌표 순서로 정렬
		Arrays.sort(polls, (s1, s2) -> Integer.compare(s1[0], s2[0]));

		// 기둥의 시작부터 끝까지 탐색하며 높은 기둥이 나올 때마다 높은 기둥수로 tallest 갱신해 result에 +=tallest
		for (int i = polls[0][0], k = 0; i <= polls[TC - 1][0]; i++) {
			if (polls[k][0] == i) {
				if (tallest < polls[k][1]) {
					tallest = polls[k][1];
				}
				k++;
			}
			result += tallest;
		}
		if (TC <= 1) {
			System.out.println(result);
			return;
		}
		// 뒷부분 처리
		//가장 높은 기둥과, 뒤에서부터 탐색한 가장 높은 기둥과의 차이를 빼주기
		//차이-> tallest-backtallest
		int backtallest = Integer.MIN_VALUE;
		int difference = 0;
		for (int i = polls[TC - 1][0], k = TC -1 ; i >= polls[0][0]; i--) {
			//i갸 기둥을 만났을 때
			if (polls[k][0] == i) {
				//앞에서부터 체크한 가장 높은 기둥 tallest와 만나면 break
				if(tallest == polls[k][1] && polls[k][0] == i) break;
				//뒤에서부터 체크한 tallest보다 현재 만난 기둥이 더 높으면 backtallest와 difference 갱신
				if (backtallest < polls[k][1]) {
					backtallest = polls[k][1];
					difference = tallest-backtallest ;
				}
				//다음 기둥
				k--;
			}
			//차이 빼주기
			result -= difference;
		}
		System.out.println(result);
	}
}

 

높은 기둥이 갱신될 때마다 tallest 변수를 갱신해 poll[0]의 x좌표부터 poll[TC-1] x좌표까지 방문하며 누적 합하고

(line 23~32)

 

가장 높은 기둥이 tallest를 만날 때까지 뒤에서부터 차이를 갱신하며 누적합에서 차이를 빼주는 방식으로 풀이하였습니다.

(line 37~57)