반응형
1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다.
2. board의 누적합을 기록한 2차원 배열 psum을 만든다.
3. psum을 활용하여 4분면으로 나누는 모든 경우에 대해 E값을 구한 뒤 최솟값을 찾는다.
1. 좌표압축으로 x, y값 범위를 N이하로 줄인 뒤, 각 좌표에 고양이들의 Z값을 기록한 2차원 배열을 board를 만든다.
좌표평면에서 유의미한 포인트들은 고양이가 위치하는 포인트들이다. 유의미한 두 좌표값 사이의 무의미한 좌표값들은 모두 같은 결과를 만들어낸다. 좌표압축으로 x, y값의 범위를 줄여주자.
2. board의 누적합을 기록한 2차원 배열 psum을 만든다.
i 사분면에 있는 Z값 합을 구하기 위해 누적합 배열 만들어둔다.
3. psum을 활용하여 4분면으로 나누는 모든 경우에 대해 E값을 구한 뒤 최솟값을 찾는다.
이제 4분면으로 나누는 모든 경우를 탐색하면서 최솟값을 찾아주면 된다. 각 경우에서의 E값은 psum을 활용하면 O(1)에 구할 수 있다. 따라서 전체 시간복잡도는 O(N^2).
반응형
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 1005, INF = 100000000;
struct Cat {
int x, y, z;
int nx, ny;
};
int N, board[MAX][MAX], psum[MAX][MAX];
Cat cats[MAX];
bool cmp_x(Cat lhs, Cat rhs) {
return lhs.x < rhs.x;
}
bool cmp_y(Cat lhs, Cat rhs) {
return lhs.y < rhs.y;
}
int min(int a, int b, int c, int d) {
return min(min(a, b), min(c, d));
}
int max(int a, int b, int c, int d) {
return max(max(a, b), max(c, d));
}
// 지도에서 (r1, c1)부터 (r2, c2)까지의 Z합
int sum(int r1, int c1, int r2, int c2) {
int ret = psum[r2][c2];
if (c1 != 0) ret -= psum[r2][c1-1];
if (r1 != 0) ret -= psum[r1-1][c2];
if (c1 != 0 && r1 != 0) ret += psum[r1-1][c1-1];
return ret;
}
// x좌표 압축
void calc_nx() {
sort(cats, cats+N, cmp_x);
int cnt = 1;
for (int i=0; i<N; i++) {
if (i != 0 && cats[i].x != cats[i-1].x) cnt++;
cats[i].nx = cnt;
}
}
// y좌표 압축
void calc_ny() {
sort(cats, cats+N, cmp_y);
int cnt = 1;
for (int i=0; i<N; i++) {
if (i != 0 && cats[i].y != cats[i-1].y) cnt++;
cats[i].ny = cnt;
}
}
// 압축한 좌표로 다시 지도를 그림
void fill_board() {
for (int i=0; i<N; i++) {
int x = cats[i].nx;
int y = cats[i].ny;
board[x][y] = cats[i].z;
}
}
void calc_psum() {
for (int i=1; i<MAX; i++) {
for (int j=1; j<MAX; j++) {
psum[i][j] = psum[i][j-1] + psum[i-1][j] - psum[i-1][j-1] + board[i][j];
}
}
}
// 2사분면의 오른쪽 꼭짓점이 x, y이도록 사분면을 나눴을 때 E값
int calc_E(int x, int y) {
int A = sum(0, 0, x, y); // 2사분면
int B = sum(x+1, 0, MAX-1, y); // 1사분면
int C = sum(0, y+1, x, MAX-1); // 3사분면
int D = sum(x+1, y+1, MAX-1, MAX-1); // 4사분면
return max(A, B, C, D) - min(A, B, C, D);
}
int find_min_E() {
int ret = INF;
for (int i=0; i<MAX; i++) {
for (int j=0; j<MAX; j++) {
ret = min(ret, calc_E(i, j));
}
}
return ret;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N;
int x, y, z;
for (int i=0; i<N; i++) {
cin >> x >> y >> z;
cats[i] = {x, y, z};
}
calc_nx();
calc_ny();
fill_board();
calc_psum();
cout << find_min_E();
return 0;
}
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
백준 11375번 열혈강호 - C++(cpp) 풀이 (0) | 2022.05.23 |
---|---|
백준 25197번 합주단 곰곰 - C++(cpp) 풀이 (0) | 2022.05.19 |
백준 1701번 Cubeditor - C++(cpp) 풀이 (0) | 2022.05.12 |
백준 1365번 꼬인 전깃줄 - C++(cpp) 풀이 (0) | 2022.05.09 |
백준 2468번 안전 영역 - C++(cpp) 풀이 (0) | 2022.05.08 |
댓글