취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 25174번 문제인 힘겨운 쿠기의 식당 개업기이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/25174 

식당의 좌표가 정수가 아니어도 된다는 조건에 유의하자.

주어진 고양이들의 각 좌표값을 고양이가 존재하는 x좌표 및 y좌표만 살려 1부터 차례대로 새로 붙여주자. 두 고양이가 같은 x좌표 또는 y좌표를 가지고 있었다면 새로 붙는 좌표 또한 동일해야한다.

이와 같은 작업을 완료하면 모든 고양이의 좌표는 1 이상 N 이하가 된다. 이제 2차원 prefix sum을 이용해 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int N, R = 0, C = 0;
pair<pair<int, int>, int> points[1000];

bool comp1(pair<pair<int, int>, int>& p1, pair<pair<int, int>, int>& p2) {
	return p1.first.first < p2.first.first;
}
bool comp2(pair<pair<int, int>, int>& p1, pair<pair<int, int>, int>& p2) {
	return p1.first.second < p2.first.second;
}

void pointsinit() {
	for (int i = 0; i < N; i++) {
		cin >> points[i].first.first >> points[i].first.second >> points[i].second;
	}

	int old = -1000000007;
	sort(points, points + N, comp1);
	for (int i = 0; i < N; i++) {
		if (points[i].first.first > old) R++;
		old = points[i].first.first;
		points[i].first.first = R;
	}

	old = -1000000007;
	sort(points, points + N, comp2);
	for (int i = 0; i < N; i++) {
		if (points[i].first.second > old) C++;
		old = points[i].first.second;
		points[i].first.second = C;
	}
}

int leftup[1002][1002], rightup[1002][1002], leftdown[1002][1002], rightdown[1002][1002];

void psuminit() {
	for (int i = 0; i < N; i++) {
		auto& p = points[i];
		int& r = p.first.first, & c = p.first.second, & z = p.second;
		leftup[r][c] += z;
		rightup[r][c] += z;
		leftdown[r][c] += z;
		rightdown[r][c] += z;
	}
	for (int r = 1; r <= R; r++) {
		for (int c = 1; c <= C; c++) {
			leftup[r][c] += leftup[r - 1][c] + leftup[r][c - 1] - leftup[r - 1][c - 1];
		}
	}
	for (int r = 1; r <= R; r++) {
		for (int c = C; c > 0; c--) {
			rightup[r][c] += rightup[r - 1][c] + rightup[r][c + 1] - rightup[r - 1][c + 1];
		}
	}
	for (int r = R; r > 0; r--) {
		for (int c = 1; c <= C; c++) {
			leftdown[r][c] += leftdown[r + 1][c] + leftdown[r][c - 1] - leftdown[r + 1][c - 1];
		}
	}
	for (int r = R; r > 0; r--) {
		for (int c = C; c > 0; c--) {
			rightdown[r][c] += rightdown[r + 1][c] + rightdown[r][c + 1] - rightdown[r + 1][c + 1];
		}
	}
}

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

	cin >> N;

	pointsinit();
	psuminit();

	int ans = 1000000007;
	for (int r = 0; r <= R; r++) {
		for (int c = 0; c <= C; c++) {
			int mx = max(max(leftup[r][c], rightup[r][c + 1]), max(leftdown[r + 1][c], rightdown[r + 1][c + 1]));
			int mn = min(min(leftup[r][c], rightup[r][c + 1]), min(leftdown[r + 1][c], rightdown[r + 1][c + 1]));
			ans = min(ans, mx - mn);
		}
	}

	cout << ans;
}