BOJ 11997 - Load Balancing (usaco silver, 차원압축)

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

 

차원압축 + 2차원 구간합 문제.

 

차원압축하는 게 어떻게하는지 잘 몰랐는데, 

https://github.com/kks227/BOJ/blob/master/11900/11997.cpp

kks227님 코드를 보며 공부했다. 항상 감사합니다 ㅜㅜ

 

#include <cstdio>
#include <set>
#include <unordered_map>
#include <algorithm>
using namespace std;

int pSum[1001][1001];

inline int rangeSum(int x1, int y1, int x2, int y2){
	return pSum[x2][y2] - pSum[x2][y1] - pSum[x1][y2] + pSum[x1][y1];
}

int main(){
	int N, x[1000], y[1000], X = 0, Y = 0;
	unordered_map<int, int> xHash, yHash;
	set<int> xSet, ySet;
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		scanf("%d %d", x+i, y+i);
		xSet.insert(x[i]);
		ySet.insert(y[i]);
	}
	for(int x: xSet)
		xHash[x] = X++;
	for(int y: ySet)
		yHash[y] = Y++;
	int A[1000][1000] = {0,};
	for(int i = 0; i < N; ++i)
		++A[xHash[x[i]]][yHash[y[i]]];
	for(int i = 0; i < X; ++i)
		for(int j = 0; j < Y; ++j)
			pSum[i+1][j+1] = pSum[i+1][j] + pSum[i][j+1] - pSum[i][j] + A[i][j];

	int result = N;
	for(int i = 0; i <= X; ++i){
		for(int j = 0; j <= Y; ++j){
			int temp = max(rangeSum(0, 0, i, j), rangeSum(i, j, X, Y));
			temp = max(rangeSum(0, j, i, Y), temp);
			temp = max(rangeSum(i, 0, X, j), temp);
			result = min(temp, result);
		}
	}
	printf("%d\n", result);
}

unordered map은 자바의 hashMap과 기능이 같다. 정렬되지않은 사전 구조로써 삽입 검색 삭제가 상수시간에 이뤄진다.

 

일단 x,y배열에 입력 값들을 받고 -> 배열에 저장된 것들을 순서대로 조회하며 xSet, ySet에 중복제거, 정렬된 값을 저장하고 -> set에 저장된 것들을 순서대로 조회하면서 상대적 순서를 xHash와 yHash에 저장한다.

ex)입력이 (3, 2), (3,7), (10,6), (11,11)인 경우 

xSet : 3, 10, 11

ySet : 2, 6, 7, 11

xHash[3] = 0, xHash[10] = 1, xHash[11] = 2;

yHash[2] = 0, yHash[6] =1, yHash[7] = 2, yHash[11] = 3;

 

x[i] = r, y[i] = c라고 하면 (xHash[r], yHash[c])가 (x[i], y[i])의 차원압축된 값이다.

(1차원압축과 다를 바 없음. 더 어려워지는 것이 아니다.)

 

차원압축만 되면 바로 풀릴 줄 알았는데, 네 구간에 포함된 소의 개수를 세는 로직을 O(4*n)으로 짜면 시간초과가 난다.

-> 2차원 구간합배열을 사용해야한다.