BOJ_2304 : 창고 다각형

👉 문제링크

2304번: 창고 다각형

---

---

🔸 문제 분석 🔸

• 주어진 기둥들을 사용해 창고를 지을때 만들 수 있는 면적 중 최소값을 출력한다.
• 조건들을 맞춰서 최소면적을 구하는 방법은 다음과 같다.
  • 가장 높은 기둥을 중심으로 왼쪽 오른쪽으로 낮아지는 지붕
  • 오목한 부분이 없어야 하므로 끝에서 가장 높은 기둥까지 다가오며, 더 큰 기둥을 만날때만 높이를 높임

🔸 코드 🔸

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

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		int n = sc.nextInt();
		int[][] pillar = new int[n][2];
		int max = 0, right = 0, mi = -1;

		for (int i = 0; i < n; i++) {
			pillar[i][0] = sc.nextInt();
			pillar[i][1] = sc.nextInt();
		}

		Arrays.sort(pillar, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});

		for (int i = 0; i < n; i++) {
			if (max < pillar[i][1]) {
				max = pillar[i][1];
				mi = i;
			}
		}

		int answer = max;
		int start = pillar[0][0], now = pillar[0][1];

		for (int i = 1; i <= mi; i++) {
			if (pillar[i][1] >= now) {
				answer += (pillar[i][0] - start) * now;
				start = pillar[i][0];
				now = pillar[i][1];
			}
		}

		start = pillar[n - 1][0];
		now = pillar[n - 1][1];

		for (int i = n - 1; i >= mi; i--) {
			if (pillar[i][1] >= now) {
				answer += (start - pillar[i][0]) * now;
				start = pillar[i][0];
				now = pillar[i][1];
			}
		}

		System.out.println(answer);
	}
}

🔸 코드 해석 🔸

• 각 기둥의 위치와 높이를 이차원 배열 pillar에 저장한다.
• pillar를 위치 기준으로 오름차순 정렬한다.
• 가장 높은 기둥의 높이와 인덱스를 저장한다.
• 맨 앞부터 가장 높은 기둥까지 창고너비를 더한다.
• 맨 뒤부터 가장 높은 기둥까지 창고 너비를 더한다.
• 가장 높은 기둥의 너비를 더한다.
• 전체 창고 너비를 출력한다.

---

🔸 end 🔸

• 예전에 python으로 풀었었는데 java로 다시 풀어보았다.
• 배열을 반복문으로 검사하는 방식으로 구현했는데, 문제 태그에 있는대로 스택으로도 구현할 수 있어보인다.