📝 문제 정보#
문제#
당신은 간식을 좋아하는 애완용 여우를 키우고 있습니다. 서로 다른 위치(데카르트 평면 위의 점으로 표현됨)에 N명의 이웃이 있으며, 각 이웃은 당신의 애완 여우에게 간식을 나눠줍니다. 각 이웃은 무제한으로 간식을 줄 수 있습니다. 원점(여우가 시작하는 위치)은 이 N개의 위치 중 하나가 아닙니다.
여우가 이 간식들을 얻기 위해 무슨 소리를 낼까요? 좋은 질문이지만, 우리의 관심사는 아닙니다.
여우는 각 위치를 방문할 때마다 정확히 하나의 간식을 얻기 위해 위치에서 위치로 이동합니다. 여우는 이전 위치를 다시 방문할 수 있지만, 연속된 두 번의 방문에서 같은 위치를 방문할 수 없습니다.
당신의 여우는 매우 게으릅니다. 각 간식을 얻은 후 여우가 이동하려는 거리는 엄격하게 감소합니다. 구체적으로, 원점에서 첫 번째 간식 위치까지의 거리는 첫 번째 간식 위치에서 두 번째 간식 위치까지의 거리보다 커야 하며, 이는 다시 두 번째 간식 위치에서 세 번째 간식 위치까지의 거리보다 커야 하고, 이런 식으로 계속됩니다.
여우가 모을 수 있는 최대 간식의 개수는 얼마입니까?
입력#
첫 번째 줄에는 정수 N (1 ≤ N ≤ 2000)이 주어집니다. 다음 N개의 줄에는 각각 X_i, 공백, Y_i가 주어지며, i = 1..N (−10,000 ≤ X_i, Y_i ≤ 10,000)으로 i번째 위치의 좌표를 나타냅니다.
출력#
출력은 하나의 정수로, 여우가 모을 수 있는 최대 간식의 개수입니다.
🧐 관찰 및 접근#
- 여우가 있을 수 있는 점의 개수는 $N$개, 방금 움직인 거리의 경우의 수는 $N^2$개 존재하는 것 같다.
- 이걸 이용해서 DP를 세울 수 있을 것 같은데, 세제곱이네..
- 어? 다시 생각해보니, 각 정점에서 신경쓸 거리는 $N$개밖에 없다!
- 잘만 하면 $O(N^2)$ DP가 성립할것만 같다.
- $\text{DP}[i][j]$: i번 정점에서 방금 움직인 거리가 j일때 최댓값 이라고 하자.
- 이때 $j$는 $i$에서 이동할 수 있는 정점들에 대한 거리를 정렬해서 쓰고, 이분탐색으로 찾으면서 진행하면 $O(N^2\log{N})$이 될 것 같다. 믿고 짜보자.
- 어떤 정점에 대해 거리가 같은 정점이 여러개 있을 수 있으므로 조심하자. 그래서 나는 index로 관리했다.
💻 풀이#
- 코드 (C++):
int calc(int cur, int idx){
if(idx == 0) return 1;
int &ret = DP[cur][idx];
if(ret != -1) return ret;
auto [d, nxt] = links[cur][idx-1];
int nidx = lower_bound(all(links[nxt]), make_pair(d, -1)) - links[nxt].begin();
ret = calc(cur, idx-1);
ret = max(ret, 1 + calc(nxt, nidx));
return ret;
}
void solve(){
cin >> N;
rep(i, 0, N) cin >> points[i].first >> points[i].second;
rep(i, 0, N) rep(j, i+1, N){
auto [x1, y1] = points[i];
auto [x2, y2] = points[j];
double dist = sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
links[i].emplace_back(dist, j);
links[j].emplace_back(dist, i);
}
rep(i, 0, N) sort(all(links[i]));
rep(i, 0, N+1) rep(j, 0, N+1) DP[i][j] = -1;
int ans = 0;
rep(i, 0, N){
auto [x1, y1] = points[i];
double dist = sqrt(x1 * x1 + y1 * y1);
int idx = lower_bound(all(links[i]), make_pair(dist, -1)) - links[i].begin();
ans = max(ans, calc(i, idx));
}
cout << ans;
}