창고 다각형

문제

언어

  • JavaScript

순서도

  1. 주어진 입력을 오름차순으로 정렬하기
  2. 가운데의 가장 높은 기둥 찾고, 그 기둥의 높이만큼 다각형의 면적에 추가
  3. 가장 왼쪽부터 가운데의 가장 높은 기둥까지, 기둥을 하나씩 비교하면서 다음 기둥이 더 크면 높이를 갱신하고 그 높이만큼 다각형의 면적에 추가
  4. 가장 오른쪽부터 가운데의 가장 높은 기둥까지, 기둥을 하나씩 비교하면서 다음 기중이 더 크면 높이를 갱신하고 그 높이만큼 다각형의 면적에 추가

문제 풀이 step 1

  • 창고의 지붕을 만들고, 그 안의 최소 면적을 구해서 출력하는 문제입니다.
  • 문제에서 5 가지 조건이 주어지는데, 그 중에서 가장 중요한 조건은 “5. 비가 올 때 물이 고이지 않도록 지붕의 어떤 부분도 오목하게 들어간 부분이 없어야 한다.” 입니다.
    • 이 조건이 왜 중요하나면, 이 조건 때문에 창고의 모양이 제한되기 때문입니다. 백준 2304번 창고 다각형 문제의 가능한 사각형의 사진
    • 위의 그림과 같이 여러 모양의 창고가 가능한데, 5 번 조건 때문에 2 번과 3 번 모양의 창고만 가능합니다.
    • 즉, 가운데 가장 높은 기둥이 있다면, 그 왼쪽에는 그보다 작거나 같은 높이의 기둥만 올 수 있습니다.
    • 그리고 그 오른쪽도 그보다 작거나 같은 높이의 기둥만 올 수 있습니다.

문제 풀이 step 2

  • 따라서, 위에서 찾은 조건에 기반한 풀이 방법은
    • 주어진 입력에서 가장 높은 기둥을 찾습니다. 그 기둥의 높이를 면적에 바로 추가해줍니다.
    • 가장 왼쪽의 기둥부터 가운데의 가장 높은 기둥까지, 각 기둥을 비교하면서 더 큰 기둥을 만나면 높이를 갱신하고, 면적 계산을 해주면 됩니다.
    • 가장 오른쪽의 기둥부터 가운데의 가장 높은 기둥까지, 각 기둥을 비교하면서 더 큰 기둥을 만나면 높이를 갱신하고, 면적 계산을 해주면 됩니다.
  • 이렇게 계산한 면적을 출력하면 정답이 됩니다.
  • 추가 설명은 주석에 작성하겠습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const solution = (input) => {
	const n = Number(input[0]);
	// 주어진 입력을 오름차순으로 정렬하기
	const warehouse = input
		.slice(1, n + 1)
		.map((v) => v.split(" ").map(Number))
		.sort((a, b) => a[0] - b[0]);

	let area = 0;
	// 가운데의 가장 높은 기둥의 index 찾기
	let max = -1;
	let center = 0;
	for (let i = 0; i < n; i++) {
		if (max < warehouse[i][1]) {
			max = warehouse[i][1];
			center = i;
		}
	}
	// 가운데의 가장 높은 기둥의 높이를 바로 면적에 추가하기
	area += warehouse[center][1];

	let nowHeight = 0;
	// 가장 왼쪽의 기둥부터 가운데의 가장 높은 기둥까지 더 높은 기둥을 만나면 높이를 갱신하면서 면적 계산하기
	for (let i = 0; i < center; i++) {
		if (warehouse[i][1] > nowHeight) nowHeight = warehouse[i][1];

		area += nowHeight * (warehouse[i + 1][0] - warehouse[i][0]);
	}

	nowHeight = 0;
	// 가장 오른쪽의 기둥부터 가운데의 가장 높은 기둥까지 더 높은 기둥을 만나면 높이를 갱신하면서 면적 계산하기
	for (let i = n - 1; i > center; i--) {
		if (warehouse[i][1] > nowHeight) nowHeight = warehouse[i][1];

		area += nowHeight * (warehouse[i][0] - warehouse[i - 1][0]);
	}

	return area;
};

console.log(solution(input));