백준 2304번 <창고 다각형>

백준 알고리즘 2304번

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

2304번: 창고 다각형

---

2304번

N개의 막대 기둥이 일렬로 세워져 있다. 이 기둥들을 이용해 면적이 가장 작은 창고를 만들어야 한다. 창고를 만드는 규칙은 아래와 같다.

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

입력으로 첫 줄에 기둥의 개수 N이 주어지고, 그 다음 N개의 줄에 걸쳐 각 기둥의 왼쪽 면의 위치 L과 기둥의 높이 H가 들어온다.

 

출력으로 면적이 가장 작은 창고 다각형의 면적을 출력하면 된다.

---

문제 해결

창고 다각형을 사각형 여러 개로 나누고 그 사각형들을 구해서 면적을 구해야겠다고 생각했다.

이를 위해서는 먼저 위치를 기준으로 정렬해야 한다.

 

가장 높은 기둥을 기준으로 왼쪽과 오른쪽으로 나눠서 생각해볼 수 있다.

• 왼쪽
  • 가장 왼쪽 기둥부터 시작해서 가장 높은 기둥까지 지붕을 이루는 기둥의 높이는 점점 높아져야 한다.
• 오른쪽
  • 가장 오른쪽 기둥부터 시작해서 가장 높은 기둥까지 지붕을 이루는 기둥의 높이는 점점 높아져야 한다.

 

처음엔 이렇게 두 가지 경우로 나눠서 면적을 구했는데 가장 높은 기둥이 여러 개 일 수도 있어서 아래의 경우를 추가해야 한다.

• 가장 높은 기둥을 포함하는 사각형을 구해야 한다.

3가지 경우에 대해 사각형을 구하는 방법은 아래와 같다.

 

왼쪽

• 가장 왼쪽 기둥부터 시작해서 가장 높은 기둥까지 지붕을 이루는 기둥의 높이는 점점 높아져야 한다.
  1. 처음엔 가장 왼쪽 기둥을 기준으로 둔다.
  2. 오른쪽으로 나아가면서 기준 기둥보다 높은 기둥 A를 찾는다. 
     • A 기둥을 찾으면 사각형이 만들어진다.
     • 기준 기둥의 높이 * (A 기둥과 기준 기둥 사이의 거리)가 해당 사각형의 면적이 된다.
  3. A 기둥을 기준 기둥으로 두고 2.를 반복한다.
  4. 만약 기둥을 둘러보다가 가장 높은 높이의 기둥을 만나면 더이상 진행하지 않는다.

가장 높은 기둥

• 가장 높은 기둥을 포함하는 사각형을 찾아야 한다.
  • 1개 
    • 해당 기둥의 면적만 더하면 된다.
  • 2개 이상
    • 가장 왼쪽에 있는 가장 높은 기둥과 가장 오른쪽에 있는 가장 높은 기둥 사이의 거리를 구하고 기둥의 높이를 곱하면 면적을 구할 수 있다.

오른쪽

• 가장 오른쪽 기둥부터 시작해서 가장 높은 기둥까지 지붕을 이루는 기둥의 높이는 점점 높아져야 한다.
  1. 처음엔 가장 오른쪽 기둥을 기준으로 둔다.
  2. 왼쪽으로 나아가면서 기준 기둥보다 높은 기둥 A를 찾는다.
     • 이때 가장 높은 기둥을 만나기 전까지 해야 한다.
     • A 기둥을 찾으면 사각형이 만들어진다.
     • 기준 기둥의 높이 * (A 기둥과 기준 기둥 사이의 거리)가 해당 사각형의 면적이 된다.
  3. A 기둥을 기준 기둥으로 두고 2.를 반복한다.

---

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int max_height = 0;
		int max_cnt = 0;

		Tuple[] columns = new Tuple[n];
		for (int i = 0; i < n; i++) {
			int p = sc.nextInt();
			int h = sc.nextInt();
			columns[i] = new Tuple(p, h);
			if (h > max_height) {
				max_height = h;
				max_cnt = 1;
			} else if (h == max_height) {
				max_cnt++;
			}
		}
		Arrays.sort(columns);

		int l = columns[0].pos;
		int r = columns[n - 1].pos;
		int idx = 0;
		int prev = 0;
		int area = 0;
		int end = 0;

		for (int i = l; i <= r; i++) {
			if (i == columns[idx].pos) {
				if (columns[idx].height == max_height) {
					end = i;
					max_cnt--;
					idx++;
					break;
				}
				if (prev < columns[idx].height) {
					prev = columns[idx].height;
				}
				idx++;
			}
			area += prev;
		}
		if (max_cnt > 0) {
			while (true) {
				if (columns[idx].height == max_height) {
					max_cnt--;
				}
				if (max_cnt == 0) {
					area += (columns[idx].pos - end) * max_height;
					end = columns[idx].pos;
					break;
				}
				idx++;
			}
		}
		area += max_height;
		idx = n - 1;
		prev = 0;
		for (int i = r; i > end; i--) {
			if (i == columns[idx].pos) {
				if (prev < columns[idx].height) {
					prev = columns[idx].height;
				}
				idx--;
			}
			area += prev;
		}
		System.out.println(area);
	}

}

class Tuple implements Comparable<Tuple> {
	int pos, height;

	public Tuple(int p, int h) {
		pos = p;
		height = h;
	}

	@Override
	public int compareTo(Tuple o) {
		if (this.pos > o.pos) {
			return 1;
		} else if (this.pos == o.pos) {
			return 0;
		} else {
			return -1;
		}
	}
}

---

결과

 

---