백준 25174 (C++) 힘겨운 쿠기의 식당 개업기

최초 업로드: 2025-07-24 00:20:42

최근 수정 시간: 2025-07-24 00:20:42

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 힘겨운 쿠기의 식당 개업기

[문제 링크](https://www.acmicpc.net/problem/25174)

## 문제 설명

가톨릭대학교에서 고양이를 대상으로 식당을 운영하려고 하는 쿠기는 식당의 위치가 중요하다고 생각해서 최적의 위치를 고민하고 있다.

쿠기는 N마리 고양이들의 집의 좌표 (X, Y)와 출출함 Z를 조사했다. 단, 고양이들의 집은 서로 같은 좌표에 존재하지 않는다.

쿠기가 사는 나라에는 "임의의 좌표를 기준으로 좌표축에 위치하는 고양이의 집이 있다면, 그 좌표에 식당을 개업할 수 없다" 라는 법이 있다. 이를 고려하여 식당의 좌표를 정하려고 하며, 식당의 좌표는 정수가 아니어도 된다.

식당을 기준으로 사분면이 있을 때, S와 E는 다음과 같다.

<ul>
	<li>Si = i 사분면에 있는 고양이들의 출출함 Z의 합</li>
	<li>E = (S1, S2, S3, S4) 중 최댓값 - (S1, S2, S3, S4) 중 최솟값</li>
	<li>i 사분면에 고양이가 한 마리도 없을 때 Si는 0이다.</li>
	<li>식당을 개업할 수 없는 좌표라면, E는 100,000,000이다.</li>
</ul>

쿠기는 E가 최솟값인 곳에 식당을 개업하려고 한다. 식당 개업 준비로 바쁜 쿠기를 도와 E의 최솟값을 구하여라.

## 입력

첫째 줄에 정수 N (4 ≤ N ≤ 1,000)이 주어진다.

둘째 줄부터 N + 1줄까지 각 고양이들의 세 정수 X (-100,000,000 ≤ X ≤ 100,000,000), Y (-100,000,000 ≤ Y ≤ 100,000,000), Z (1 ≤ Z ≤ 1,000)가 주어진다.

## 출력

E의 최솟값을 출력한다.

## 풀이
#### N이 최대 1000이고, 좌표 간의 거리가 멀어서 좌표 압축으로 2000 x 2000 공간에 매핑시켜 2차원 누적합으로 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

int preSum[2001][2001];

struct element {
    int a, b, c;
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;

// 좌표 압축
 vector<element> v(n);
 vector<int> vals;
 for(int i=0;i<n;i++) {
 cin >> v[i].a >> v[i].b >> v[i].c;
 vals.push_back(v[i].a);
 vals.push_back(v[i].b);
 }
 sort(vals.begin(), vals.end());
 vals.erase(unique(vals.begin(), vals.end()), vals.end());

// 누적합 계산
 for(int i=0;i<n;i++) {
 int a = lower_bound(vals.begin(), vals.end(), v[i].a) - vals.begin() + 1;
 int b = lower_bound(vals.begin(), vals.end(), v[i].b) - vals.begin() + 1;
 preSum[a][b] += v[i].c;
 }
 for(int i=1;i<=2000;i++) {
 for(int j=1;j<=2000;j++) {
 preSum[i][j] += preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1];
 }
 }

int minE = INT_MAX;
 for(int i=1;i<=2000;i++) {
 for(int j=1;j<=2000;j++) {
 int S1 = preSum[i][j];
 int S2 = preSum[2000][j] - preSum[i][j];
 int S3 = preSum[i][2000] - preSum[i][j];
 int S4 = preSum[2000][2000] - preSum[2000][j] - preSum[i][2000] + preSum[i][j];
 minE = min(minE, max({S1, S2, S3, S4}) - min({S1, S2, S3, S4}));
 }
 }
 cout << minE;
}
```