[백준 10272] 현상금 사냥꾼 김정은

dp문제 였는 데 풀고 찾아보니까 바이토닉 투어라는 문제로 유명했다.

1. 풀이

이 문제를 보고 직접해보면 같은 점을 지나면 무조건 손해이다. 그렇다면 가는 경로와 다시 오는 경로는 겹치지 않는다. 이 아이디어를 잘 생각해보면 dp로 문제가 해결이 가능하다.

$$dp[pos][last]\;=\;현재\;pos의점을\;보고있고,\;연결할\;수\;있는\;후보가\;pos−1과\;last일때$$

이 상태전이가 이해가 안된다면 직접해보면 금방 알 수 있을 것이다. 각 어떤 점을 볼때 위의 아이디어처럼 이을려고하면 \(pos−1,\;last\)밖에 후보가 나오지 않는다.

$$dp[pos][last]=min(dp[pos+1][last]+dst(pos,pos−1),dp[pos+1][pos−1]+dst(pos,last))$$

이처럼 \(pos,\;pos−1\)과 \(pos,\;last\)를 연결하는 경우를 고려해주면 문제를 풀 수 있다.

2.소스 코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;


int n;
int X[513], Y[513];
double dp[513][513];


double dst(int a, int b) {
    int dx = X[a] - X[b];
    int dy = Y[a] - Y[b];
    return sqrt(1.0 * dx * dx +  1.0*dy * dy);
}


double solve(int pos, int last) {
    if (pos == n+1)
        return dst(pos-1, last);


    double& ret = dp[pos][last];
    if (ret >= 0) return ret;


    if (last == 0) last = 1;


    ret = 1e9;
    ret = min(ret, solve(pos+1, last)+dst(pos, pos-1));
    ret = min(ret, solve(pos+1, pos-1)+dst(pos, last));


    return ret;
}


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


    cout << fixed;
    cout.precision(3);


    int tc; cin >> tc;
    while (tc--) {
        cin >> n;
        for (int i = 0; i <= 512; i++)
            fill(dp[i], dp[i]+513, -1);
        memset(X, 0, sizeof(X));
        memset(Y, 0, sizeof(Y));


        for (int i = 1; i <= n; i++) 
            cin >> X[i] >> Y[i];


        X[0] = X[1]; Y[0] = Y[1];
        cout << solve(1, 1) << "\n";
    }


    return 0;
}