[백준 2304] 창고 다각형 (C++)

풀이

약간 도미노를 생각하면 편할 것 같다.

 

왼쪽부터 간다고 생각하면 다음과 같다.

3 ~ 4 의 구간은 비록 높이가 0인 다각형이지만 2 ~ 3 구간에서의 높이가 4이기 때문에 3 ~ 4 구간의 높이도 4가 된다.

5 ~ 6 의 구간은 비록 높이가 3인 다각형이지만 4 ~ 5 구간에서의 높이가 6이기 때문에 5 ~ 6 구간의 높이도 6이 된다.

즉 나보다 한 칸 옆에서의 높이가 나의 높이보다 크다면 그것으로 갱신해준다.

	for (int i = 1; i <= 1000; i++)
		area[i] = max(height[i], area[i - 1]);

 

오른쪽부터 간다고 생각하면 다음과 같다.

15 ~ 16 구간은 높이가 8인 다각형이지만 현재 area 는 10으로 되어있다. 따라서 더 작은 값으로 갱신하면 된다.

14 ~ 15 구간을 보자.

높이가 0인 다각형이지만 현재 area 는 10으로 되어있다.

문제에 따르면 이 구간의 높이는 8이 되야한다.

한 칸 오른쪽에서의 넓이 area가 현재 높이보다 크다면 더 큰 값인 10으로 갱신한다.

그리고 나서 현재 area 와 비교해서 더 작은 값으로 갱신하면 8이 된다.

7 ~ 8 구간을 보자.

현재의 높이는 0이고, 한 칸 오른쪽에서의 넓이 area가 현재 높이보다 크다면 더 큰 값인 10으로 갱신한다.

그리고 나서 현재 area와 비교해서 더 작은 값으로 갱신하면 6이 된다.

	for (int i = 1000; i >= 0; i--)
		area[i] = min(area[i], max(height[i], area[i + 1]));

 

왼쪽과 오른쪽을 통해서 얻은 area 를 다 더해주면 창고 다각형의 넓이를 구할 수 있게 된다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int n;
int height[1001];
int area[1001];
int main()
{
	cin >> n;
	while (n--)
	{
		int L, H;
		cin >> L >> H;
		height[L] = H;
	}

	// left
	for (int i = 1; i <= 1000; i++)
		area[i] = max(height[i], area[i - 1]);

	// right
	for (int i = 1000; i >= 0; i--)
		area[i] = min(area[i], max(height[i], area[i + 1]));

	int ret = 0;
	for (int i = 1; i <= 1000; i++)
		ret += area[i];

	cout << ret << '\n';
	return 0;
}