BOJ 2304 창고 다각형

사용한 알고리즘

구현

알고리즘 설명

우선 높이가 큰 순으로 정렬 한다.
높이가 가장 높은 사각형을 기준으로 문제를 좌우로 나눈다.
좌측에서 가증 높은 사각형 다음 위치를 찾아서 그 사이에 찾아지는 사각형을 더한다.
우측 또한 이를 반복한다.
사각형을 찾을 때, x축이 전에 사각형 위치에 포함되지 않아야 한다.
결과를 출력한다.

풀이

// baekjoon 2304 yechan
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
const int MAX_N = 1001;
typedef pair<int,int> P;

int N;
P point[MAX_N];

int main() {
	scanf("%d", &N);
	for (int i=0; i<N; i++)
		scanf("%d%d", &point[i].second, &point[i].first);

// 높이가 큰 순서로 내림차순 정렬
	sort(point, point+N, greater<pair<int,int> >());

// 중앙 위치 좌표
	int mid = point[0].second;
	int left = mid, right = mid;

// 중앙 위치 높이
	int ret = point[0].first;
	for (int i=1; i<N; i++) {
// 현재 적용한 높은 위치의 왼쪽보다 작으면서 다음으로 높은 높이
		if (point[i].second < left) {
			ret += point[i].first * (left-point[i].second);
			left = point[i].second;
		}
// 현재 적용한 높은 위치의 오른족보다 크면서 다음으로 높은 높이
		if (point[i].second > right) {
			ret += point[i].first * (point[i].second-right);
			right = point[i].second;
		}
	}
	printf("%d\n", ret);
	return 0;
}