백준 2304: 창고 다각형

문제 요약

기둥들의 위치와 높이가 주어질 때, 가장 작은 창고 다각형의 면적을 구하는 프로그램을 작성하시오.

문제 분류

• 자료 구조
• 브루트포스 알고리즘
• 스택

문제 풀이

문제 분류 자체는 스택이지만, 스택없이 map과 역방향 반복자를 이용하면 풀 수 있다.

맵으로 먼저 오름차순 정렬 후, 순방향 반복자와 역방향 반복자를 이용하여 그림의 왼쪽부터 순회 및 오른쪽으로 순회하며 넓이를 계산해나가면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int main()
{
	int n;
	int in1, in2;
	map<int, int> m;
	int res = 0, max, maxr = 0, maxl = 0;

	cin >> n;
	for (int i = 0; i < n; i++) {
		scanf("%d%d", &in1, &in2);
		m.insert({ in1, in2 });
	}
	maxl = m.begin()->first;
	max = m.begin()->second;
	for (auto& x : m) {
		if (max < x.second) {
			res += (x.first - maxl) * max;
			max = x.second;
			maxl = x.first;
		}
	}
	maxr = m.rbegin()->first;
	max = m.rbegin()->second;
	for (auto it = m.rbegin(); it != m.rend(); it++) {
		if (max < it->second) {
			res += (maxr - it->first) * max;
			max = it->second;
			maxr = it->first;
		}
	}
	res += (maxr - maxl + 1) * max;
	cout << res;
	return 0;
}