백준 17371: 이사

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

 

이 문제는 몇 번 맞닥뜨렸지만, 예제를 보고, 내가 모르는 공식이 있어서 풀기 어려울거라 생각해서 계속 넘어갔었다.

그런데 오늘, 다시 마주했을 때, 풀 수 있을 것 같다는 자신감이 갑자기 생겨서, 풀이를 고민하였다.

 

일단 예제에선 소수가 눈에 띄는데, 내가 아는 알고리즘 내에서 이 문제에 적용할 수 있고, 소수가 사용되는 것으로 이분 탐색이 막연히 떠올랐다. 그런데, 문제의 분류를 보니 "스페셜 저지"가 보였다. 즉, 예제의 답은 많은 답 중 하나일 것이다. 란 생각에 이르렀고, 만약 이 문제가 내가 아는 공식 내에서 풀 수 있는 문제라면, 단순하게 생각을 해보자까지 이르렀다.

 

다시 말해서

이 예제는 혼선을 주기 위한 페이크이고, 단순한 것이 답이다란 것이다.

 

그러자, 나는 이전에 해결했던 문제가 하나 떠올랐다.

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

 

위의 문제의 답은 마을의 위치가 답이다. 그러면, 이 문제도, 편의점의 위치가 답이 아닐까?

만약 그렇다면, 답은 가장 먼 거리만 고려하면 된다. 그렇게 나온 코드는 다음과 같다.

#include <iostream>
#include <cmath>

using namespace std;

int N, X[1001], Y[1001], ansx, ansy;
double D = 1000000007;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N;
	cout << fixed;
	cout.precision(7);
	for (int i = 0; i < N; i++)
	{
		cin >> X[i] >> Y[i];
	}
	for (int i = 0; i < N; i++)
	{
		double d = 0;
		for (int j = 0; j < N; j++)
		{
			if (i == j) continue;
			d = max(d, sqrt(pow(X[i] - X[j], 2) + pow(Y[i] - Y[j], 2)));
		}

		if (D >= d)
		{
			D = d;
			ansx = X[i];
			ansy = Y[i];
		}
	}
	cout << ansx << " " << ansy << '\n';
}

 

 

제출 결과 한번에 "맞았습니다"를 얻었다. 다만 증명을 하기 어려울 것 같다.

예제가 문제 난이도를 올리는 특이한 문제였다.

 

PS)

이 문제 해결로, 1024일 연속 문제를 해결했다. 더 정진하도록하자.