개요

백준11997

• 입력
  The first line of the input contains a single integer, (N). The next (N) lines each contain the location of a single cow, specifying its (x) and (y) coordinates.

• 출력
  You should output the smallest possible value of (M) that FJ can achieve by positioning his fences optimally.

접근 방식

1. 배열을 통해 0,0부터 i,j까지의 좌표에 소가 몇마리있는지 미리 저장해주는 방식을 사용했다.

2. 그어지는 선은 짝수로만 들어오니 x2를 해줘서 SetMinAn함수에 넣어준 후,
   두 선으로 나눠진 영역의 소갯수중 최대값을 구하는 방식을 사용했으나,
   문제는 소의 갯수가 최대 1000개고, 좌표는 최대 100만까지 올라가서 배열이 메모리가 너무 커진다.

3. 따라서 검색해본 결과, 소의 마릿수는 1000개에 불과하므로,
   좌표를 압축해야한다.

4. 좌표 압축방법은

   1. 소의 좌표를 x,y로 나눠서 stl의 set자료구조에 넣음으로 중복값 제거 및 오름차순으로 정렬해준다.
   2. 정렬된 좌표들을 stl의 unordered_map을 이용한 hashmap에
      key값으로 넣고 value값들을 0부터 1씩 증가시키며 저장한다.
   3. 그 후 소의 원래 좌표들을 hashmap을통해 x,y좌표를 압축된 좌표로 변형시켜서 배열에 저장하면 된다.

      //set을 통해 처음 좌표들을 중복없이 오름차순으로 정렬하기
      set<int> xSet, ySet;
      //set에 들어온 좌표들을 HashMap을 통해서 좌표들을 순서대로 압축한다.
      unordered_map<int, int> xHash, yHash;
      //압축후 좌표를 저장할 배열
      int afterComp[1001][1001];
      
      for (int i = 0; i < N; i++) {
      		cin >> X[i];
      		cin >> Y[i];
      		//set에 좌표들을 넣어 중복을 제거한후 오름차순 정렬
      		xSet.insert(X[i]);
      		ySet.insert(Y[i]);
      	}
      	//hashmap에 set의 좌표들을 넣어 0뷰터 순서대로 압축시켜준다. 
      	for (int i : xSet) {
      		xHash[i] = xCnt++;
      	}
      	for (int i : ySet) {
      		yHash[i] = yCnt++;
      	}
      	//hashmap을 통해 압축을 한 좌표들을 afterComp에 대입시킨후 소가 있다는 표시로 ++을 해줌
      	for (int i = 0; i < N; i++) {
      		afterComp[xHash[X[i]]][yHash[Y[i]]]++;
      	}

5. 그 후, 압축된 x좌표의 갯수인 xCnt, 압축된 y좌표의 갯수인 yCnt를 통해 압축된 전체 좌표의 배열에서 누적합을 계산해 누적합배열을 만든다.

   		//모든 압축 후의 좌표에 대해 누적 소 갯수값을 다 저장  
   		for (int i = 0; i < xCnt; i++) {
   			for (int j = 0; j < yCnt; j++) {
   				howManyCows[i + 1][j + 1] = howManyCows[i + 1][j]
               + howManyCows[i][j + 1] - howManyCows[i][j] + afterComp[i][j];
   			}
   		}

6. 그 후 누적합 배열에서 모든 좌표에서 가로선 세로선을 그어 나눠진 사분면에서 소의 갯수들을 비교하여 최대값을 비교한다.

   		//0,0부터 xCnt-1,yCnt-1값까지 모든 좌표에 가로 세로 선 두개를 그어서 각 사분면의 제일큰 소의 갯수를 비교해본다.
   		for (int i = 0; i <= xCnt; i++) {
   			for (int j = 0; j <= yCnt; j++) {
   				int tmpMaxPartialCowSum = 1'000'001;
   				tmpMaxPartialCowSum = max(howManyCows[i][j],howManyCows[xCnt][j]-howManyCows[i][j]);
   				tmpMaxPartialCowSum = max(tmpMaxPartialCowSum, howManyCows[i][yCnt]-howManyCows[i][j]);
   				tmpMaxPartialCowSum = max(tmpMaxPartialCowSum, 
   					howManyCows[xCnt][yCnt] - howManyCows[xCnt][j] - howManyCows[i][yCnt] + howManyCows[i][j]);
   				//위의 식을 거쳐 tmpMaxPartialCowSum에 i,j일때의 각 사분면의 제일 큰 소의 갯수가 저장됨.
   				//minCowSum을 갱신
   				minCowSum = min(tmpMaxPartialCowSum,minCowSum);
   			}
   		}

전체 코드

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<set>

using namespace std;
//set을 통해 처음 좌표들을 중복없이 오름차순으로 정렬하기
set<int> xSet, ySet;
//set에 들어온 좌표들을 HashMap을 통해서 좌표들을 순서대로 압축한다.
unordered_map<int, int> xHash, yHash;
//압축 전 100만까지의 좌표들
int beforeCompX[1001];
int beforeCompY[1001];
//압축후 좌표를 저장할 배열
int afterComp[1001][1001];
//0,0 부터 (i,j)좌표까지 
int howManyCows[1001][1001];
int minCowSum = 1'000'001;

int main() {
	int N=0, cowX=0, cowY=0,X[1001],Y[1001],xCnt=0,yCnt=0;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> X[i];
		cin >> Y[i];
		//set에 좌표들을 넣어 중복을 제거한후 오름차순 정렬
		xSet.insert(X[i]);
		ySet.insert(Y[i]);
	}
	//hashmap에 set의 좌표들을 넣어 0뷰터 순서대로 압축시켜준다. 
	for (int i : xSet) {
		xHash[i] = xCnt++;
	}
	for (int i : ySet) {
		yHash[i] = yCnt++;
	}
	//hashmap을 통해 압축을 한 좌표들을 afterComp에 대입시킨후 소가 있다는 표시로 ++을 해줌
	for (int i = 0; i < N; i++) {
		afterComp[xHash[X[i]]][yHash[Y[i]]]++;
	}
	//모든 압축 후의 좌표에 대해 누적 소 갯수값을 다 저장  
	for (int i = 0; i < xCnt; i++) {
		for (int j = 0; j < yCnt; j++) {
			howManyCows[i + 1][j + 1] = howManyCows[i + 1][j] + howManyCows[i][j + 1] - howManyCows[i][j] + afterComp[i][j];
		}
	}

	//0,0부터 xCnt-1,yCnt-1값까지 모든 좌표에 가로 세로 선 두개를 그어서 각 사분면의 제일큰 소의 갯수를 비교해본다.
	for (int i = 0; i <= xCnt; i++) {
		for (int j = 0; j <= yCnt; j++) {
			int tmpMaxPartialCowSum = 1'000'001;
			tmpMaxPartialCowSum = max(howManyCows[i][j],howManyCows[xCnt][j]-howManyCows[i][j]);
			tmpMaxPartialCowSum = max(tmpMaxPartialCowSum, howManyCows[i][yCnt]-howManyCows[i][j]);
			tmpMaxPartialCowSum = max(tmpMaxPartialCowSum, 
				howManyCows[xCnt][yCnt] - howManyCows[xCnt][j] - howManyCows[i][yCnt] + howManyCows[i][j]);
			//위의 식을 거쳐 tmpMaxPartialCowSum에 i,j일때의 각 사분면의 제일 큰 소의 갯수가 저장됨.
			//minCowSum을 갱신
			minCowSum = min(tmpMaxPartialCowSum,minCowSum);
		}
	}
	cout << minCowSum;
}

문풀후생

좌표를 압축하여 큰 숫자를 다루는게 좀 신기했다.
방법을 알았으니 잘 사용해야겠다.