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일 연속 문제를 해결했다. 더 정진하도록하자.
'알고리즘 문제 풀이 일지' 카테고리의 다른 글
백준 1119: 그래프 (1) | 2024.08.20 |
---|---|
백준 2378: 불필요한 수 (0) | 2024.08.18 |
백준 1687: 행렬 찾기 (0) | 2024.08.10 |
백준 7573: 고기잡이 (0) | 2024.08.07 |
백준 2957: 이진 탐색 트리 (0) | 2024.08.03 |