백준 25174번 힘겨운 쿠기의 식당 개업기 - C++(cpp) 풀이

---

 

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;
}