[백준] 창고 다각형 2304번 C++ 풀이

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

2304번: 창고 다각형

#include <iostream>
#include <algorithm>
using namespace std;
int N;
int max_pos, max_h; // 최대 높이의 위치와 높이
int arr[1001];
int res = 0
int main(void)
{
	int L, H;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		cin >> L >> H;
		arr[L] = H;
		if (max_h < H)
		{
			max_pos = L;
			max_h = H;
		}
	}

	int Lh=0; // 왼쪽 영역의 최고 높이
	for (int i = 1; i <max_pos; i++)
	{
		Lh = max(Lh, arr[i]);
		res += Lh;
	}

	int Rh=0; // 오른쪽 영역의 최고 높이
	for (int i = 1000; i > max_pos; i--)
	{
		Rh = max(Rh, arr[i]);
		res += Rh;
	}

	cout << res + max_h;

}

위 그림처럼 최대 높이의 인덱스를 기준으로 왼쪽 영역과 오른쪽 영역의 넓이를 구하면 됩니다.

왼쪽 영역은 0부터 시작해 최대 높이의 인덱스 전까지 매 인덱스마다 현재까지의 최대 높이를 더해주고

매 인덱스 탐색마다 현재까지의 최대 높이가 더 높아질 경우 갱신해주면 됩니다.

마찬가지로 오른쪽 영역의 넓이를 구하고

그 결과에 최대 높이를 더해주면 됩니다.