개요
-
입력
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.
접근 방식
-
배열을 통해 0,0부터 i,j까지의 좌표에 소가 몇마리있는지 미리 저장해주는 방식을 사용했다.
-
그어지는 선은 짝수로만 들어오니 x2를 해줘서 SetMinAn함수에 넣어준 후,
두 선으로 나눠진 영역의 소갯수중 최대값을 구하는 방식을 사용했으나,
문제는 소의 갯수가 최대 1000개고, 좌표는 최대 100만까지 올라가서 배열이 메모리가 너무 커진다. -
따라서 검색해본 결과, 소의 마릿수는 1000개에 불과하므로,
좌표를 압축해야한다. -
좌표 압축방법은
- 소의 좌표를 x,y로 나눠서 stl의 set자료구조에 넣음으로 중복값 제거 및 오름차순으로 정렬해준다.
- 정렬된 좌표들을 stl의 unordered_map을 이용한 hashmap에
key값으로 넣고 value값들을 0부터 1씩 증가시키며 저장한다. - 그 후 소의 원래 좌표들을 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]]]++; }
-
그 후, 압축된 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]; } } -
그 후 누적합 배열에서 모든 좌표에서 가로선 세로선을 그어 나눠진 사분면에서 소의 갯수들을 비교하여 최대값을 비교한다.
//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;
}문풀후생
좌표를 압축하여 큰 숫자를 다루는게 좀 신기했다.
방법을 알았으니 잘 사용해야겠다.
코딩 창고!