[백준/BOJ] 백준 11997번 : Load Balancing (Silver)

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

11997번: Load Balancing (Silver)

 

좌표 값의 범위는 큰 반면, N의 범위는 작으므로, 좌표 값을 크기 순으로 정렬한 뒤, 크기 순으로 id를 부여하여 좌표 압축 (값 압축)을 수행했다. 그리고 기존 좌표가 아닌 부여한 id 값을 기반으로 2차원 누적합을 수행하여, 4개의 구역을 비교하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
using namespace std;

//좌표 압축을 하고, 2차원 누적합을 통해 문제 해결

int n;
vector<pair<int, int>> point;
vector<int> number;
unordered_map<int, int> number_id; //좌표값 -> 좌표값을 크기순으로 부여한 id 로 좌표 압축

int board[2005][2005]; //압축 시킨 좌표
int psum[2005][2005]; //2차원 누적합

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 0; i < n; i++) {
		int x, y;
		cin >> x >> y;
		point.push_back(make_pair(x, y));

		number.push_back(x);
		number.push_back(y);
	}

	sort(number.begin(), number.end());
	number.erase(unique(number.begin(), number.end()), number.end());

	//좌표 앞축 (좌표값 -> 크기 순서대로 새로운 id 부여한 값)
	for (int i = 0; i < number.size(); i++) {
		number_id.insert(make_pair(number[i], i + 1));
	}

	for (int i = 0; i < point.size(); i++) {
		board[number_id[point[i].first]][number_id[point[i].second]]++;
	}

	for (int i = 1; i < 2005; i++) {
		for (int j = 1; j < 2005; j++) {
			psum[i][j] = psum[i][j - 1] + psum[i - 1][j] - psum[i - 1][j - 1] + board[i][j];
		}
	}

	int result = 987654321;

	for (int i = 1; i <= 2000; i++) {
		for (int j = 1; j <= 2000; j++) {
			int area1 = psum[i][j];
			int area2 = psum[i][2000] - psum[i][j];
			int area3 = psum[2000][j] - psum[i][j];
			int area4 = psum[2000][2000] - area1 - area2 - area3;
			result = min(result, max(max(area1, area2), max(area3, area4)));
		}
	}

	cout << result;

	return 0;
}