취미로 코딩하기

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

이번에 볼 문제는 백준 2187번 문제인 점 고르기이다.
문제는 아래 링크를 확인하자.

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

어떤 두 점의 두 가중치가 직사각형에 포함된 점들의 가중치 중 가장 큰 수와 작은 수가 되기 위해서는 이 두 점이 같은 직사각형 안에 있을 수 있어야 함을 관찰하자. 두 점이 같은 직사각형에 포함되어 있을 수 있는지의 여부는 두 점의 좌표의 차를 이용해 간단하게 판별할 수 있다.

한편, 여기서 더 나아가 같은 직사각형에 포함되어 있을 수 있는 두 점의 쌍들을 전부 살펴 그 가중치 차의 최댓값을 찾는 것으로 문제를 해결할 수 있음을 보일 수 있다. 모든 두 점의 쌍을 확인하므로 정답이 되는 경우의 두 점의 쌍을 무조건 확인하며, 답을 구성하는 경우가 아닌 모든 경우는 (1) 두 점이 직사각형의 가장 크고 작은 두 가중치를 이루지 못하거나 (2) 두 가중치의 차가 답보다 작다는 점을 이용하면 이를 어렵지 않게 보일 수 있다.

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

#include <iostream>
using namespace std;

int N, A, B;
int X[1000], Y[1000], C[1000];
int ans;

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

	cin >> N >> A >> B;
	for (int i = 0; i < N; i++) cin >> X[i] >> Y[i] >> C[i];
	for (int i = 0; i < N; i++) {
		for (int j = i + 1; j < N; j++) {
			if (abs(X[i] - X[j]) < A && abs(Y[i] - Y[j]) < B) {
				ans = max(ans, abs(C[i] - C[j]));
			}
		}
	}

	cout << ans;
}