쌓고 쌓다

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

알고리즘/백준

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

승민아 2022. 1. 1. 16:31

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

 

2304번: 창고 다각형

첫 줄에는 기둥의 개수를 나타내는 정수 N이 주어진다. N은 1 이상 1,000 이하이다. 그 다음 N 개의 줄에는 각 줄에 각 기둥의 왼쪽 면의 위치를 나타내는 정수 L과 높이를 나타내는 정수 H가 한 개의

www.acmicpc.net

#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부터 시작해 최대 높이의 인덱스 전까지 매 인덱스마다 현재까지의 최대 높이를 더해주고

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

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

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

Comments