BOJ 11997 Load Balancing (Silver)

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

11997번: Load Balancing (Silver)

 

N이 많이 작아 (n <= 1000) 2-D 구간합을 사용하면 쉽게 풀 수 있는 문제였다.
하지만 문제는 좌표의 의 범위가 매우 크다는 것이였다. 나는 이것을 좌표압축을 이용하여 1,000,000 범위를 2000 이하로 줄여 문제를 풀 수 있었다.

아쉬웠던 것은 set, map을 사용했다는 것이다. 메모리를 많이 잡아먹었을 뿐 아니라 시간이 매우 오래 걸렸다.

 

#include <cstdio>
#include <set>
#include <map>
#include <vector>
using namespace std;
//x,y : 1 ~ 1000000

int n;
int board[2010][2010];
int psum[2010][2010];
map<int, int> m;
vector<pair<int, int>> point;

int get_psum(int sr, int sc, int er, int ec){
	return psum[er][ec] - psum[sr-1][ec] - psum[er][sc-1] + psum[sr-1][sc-1];
}
int main() {
	
	set<int> s;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		int a, b; scanf("%d%d",&a,&b);
		point.push_back({a,b});
		s.insert(a);
		s.insert(b);
	}
	
	int idx = 1;
	for(auto it = s.begin(); it != s.end(); ++it) m[*it] = idx++;
	for(auto p : point) ++board[m[p.first]][m[p.second]];
	
	for(int i=1;i<idx;i++){
		for(int j=1;j<idx;j++){
			psum[i][j] = board[i][j] + psum[i-1][j] + psum[i][j-1] - psum[i-1][j-1];
		}
	}
	
	int answer = n;
    
	for(int i=1;i<idx;i++){
		for(int j=1;j<idx;j++){
			int lu = get_psum(1,1,i,j);
			int ld = get_psum(i+1,1, idx-1, j);
			int ru = get_psum(1, j+1, i, idx-1);
			int rd = get_psum(i+1,j+1, idx-1, idx-1);
			
			int b = max(max(max(lu,ld),ru),rd);
			if(b < answer) answer = b; 
		}
	}
	
	printf("%d\n",answer);
	
	return 0;
}

 

PS. 실행시간/메모리 1등,2등 코드를 보니 다양한 풀이법이 있는 문제였다. 2등분의 코드는 더 어려운 알고리즘을 사용하셨지만, 코드가 굉장이 깔끔해서 배울 점이 많은 코드였다.