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

문제

2304번: 창고 다각형

예시의 그림처럼 각 기둥의 천장을 이어서 만든 넓이를 구하는 문제입니다.

스택을 이용하여 풀 수 도 있지만 다른 방법을 사용하여 풀어 보았습니다.

간단히 말하면 먼저 기둥 중에서 가장 높은 기둥을 구하고 그 기둥을 기준으로 양쪽으로 나누어 넓이를

따로 구해주었습니다.

int n;
cin >> n;
vector<pair<int, int>>v(n);
pair<int, int> top = { 0,0 };
for (int i = 0; i < n; i++) {
	cin >> v[i].first >> v[i].second;
	if (v[i].second > top.second)
		top = v[i];

}
sort(v.begin(), v.end());

기둥의 갯수인 n을 입력받습니다.

벡터의 종류를 pair로 받았는데 first가 기둥의 위치 이고 second가 기둥의 높이입니다.

변수 top은 기둥의 높이가 가장 큰 수가 들어갑니다.

다 입력받은 기둥은 first(위치)를 기준으로 정렬합니다.

int ans = 0;
int max = 0;
	
for (int i = 0; v[i] <= top; i++) {
	if (v[i] == top) {
		ans += (top.first-v[max].first)*v[max].second;
		ans += top.second;
		max = i;
		break;
	}
	if (v[max].second <= v[i].second) {
               ans += (v[i].first - v[max].first) * v[max].second;			
               max = i;
	}
}

왼쪽 부터 top까지 넓이를 구합니다.

변수 ans는 넓이 이고 max는 기둥의 맨처음 위치부터 돌면서 더 큰 기둥의 위치가 나오면 계속 갱신합니다.

for문을 돌다가 top에 도달하면 top의 기둥을 포함해서 넓이를 더해주고 멈춥니다.

int min = n - 1;
for (int i = n - 1; i >= max; i--) {
	if (i == max) {
		ans += (v[min].first - v[max].first) * v[min].second;
		break;
	}
	if (v[min].second <= v[i].second) {
		ans += (v[min].first - v[i].first) * v[min].second;
		min = i;
	}
}
cout << ans;

이제는 맨 마지막 기둥 부터 top까지 반복하면서 위의 코드 처럼 반복해주고

마지막에 ans를 출력하면 됩니다.

---

전체코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
using namespace std;
using ll = long long;
using ull = unsigned long long;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	vector<pair<int, int>>v(n);
	pair<int, int> top = { 0,0 };
	for (int i = 0; i < n; i++) {
		cin >> v[i].first >> v[i].second;
		if (v[i].second > top.second)
			top = v[i];

	}
	sort(v.begin(), v.end());

	int ans = 0;
	int max = 0;
	
	for (int i = 0; v[i] <= top; i++) {
		if (v[i] == top) {
			ans += (top.first-v[max].first)*v[max].second;
			ans += top.second;
			max = i;
			break;
		}
		if (v[max].second <= v[i].second) {
			ans += (v[i].first - v[max].first) * v[max].second;
			max = i;
		}
	}
	int min = n - 1;
	for (int i = n - 1; i >= max; i--) {
		if (i == max) {
			ans += (v[min].first - v[max].first) * v[min].second;
			break;
		}
		if (v[min].second <= v[i].second) {
			ans += (v[min].first - v[i].first) * v[min].second;
			min = i;
		}
	}
	cout << ans;



	return 0;
}