[BOJ] 10272 : 현상금 사냥꾼 김정은

문제 링크

10272번: 현상금 사냥꾼 김정은 (acmicpc.net)

10272번: 현상금 사냥꾼 김정은

 

풀이

내가 감히 풀 수 없을 정도로 어려웠던 DP 문제.

정은이는 왼쪽에서 오른쪽으로 갈 떄는 X좌표가 오름차순이 되도록 행성을 방문하고, 반대로 오른쪽에서 왼쪽으로 갈 때는 X좌표가 내림차순이 되도록 방문해야한다. 또한 최소한의 거리로 행성을 모두 방문해야한다.

최소한의 거리로 모든 행성을 방문해야하기 때문에 같은 행성을 두 번 방문하는 경우는 없다!

무조건 제일 끝 행성을 찍고 출발점으로 돌아오는 방식이기 때문에

출발점~끝점 + 끝점~ 출발점. 따라서 출발점과 끝점은 두 번 방문하는 것과 같다.

그렇기 때문에 두 개의 다른 우주선이 출발점에서 동시에 출발해서 서로 겹치지 않고 끝점에 도달한다고 생각하면 편하다.

허접하게 그림을 그려보자면 이렇게 된다.  A는 1->2->4->5 순으로 방문했고, B는 1->3->5 순으로 방문했다고 하자. 두 경로를 합치면 1->2->4>-5->3->1 순으로 방문한 거리와 똑같다.

DP[i][j] 는 한 우주선은 현재 i번째 행성에 방문했고, 다른 우주선은 j번째 행성에 방문했을 때 거리합의 최소이다.

그리고 다음 행성은 max(i,j) + 1번째 행성이라고 할 수 있으며, 현재 i번째 행성에 있는 우주선1이 갈 수도 있고 j번째 행성에 있는 우주선2가 갈 수도 있다.

재귀함수를 travel 이라고 하고 max(i,j) + 1 = K 라고 하면

DP[i][j] = min(travel( K , j ) + distance( i , K ) , travel( i , K ) + distance( j , K )) 로 나타낼 수 있다.

1. travel( K , J ) 는 i 에 있던 우주선이 움직였다는 것이므로 distance( i , K )를 더해준다.

2. travel( i , K ) 는 j 에 있던 우주선이 움직였다는 것이므로 distance( j , K ) 를 더해준다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <string.h>
#include <string>
#include <stack>
#include <vector>
#include <math.h>
#include <queue>
#include <climits>
#include <algorithm>
#include <iomanip>
#include <map>
#define mod 1000000007
using namespace std;
typedef long long ll;
typedef priority_queue<pair<pair<int, int>, int>, vector<pair<pair<int, int>, int>>, greater<pair<pair<int, int>, int>>> Priority_queue;
const int INF = INT_MAX;
const int MAX_N = 512 + 5;
vector<pair<int, int>> planet;
double DP[MAX_N][MAX_N];
int T, N;
 
double distance(pair<int, int> X, pair<int, int> Y) {
    return sqrt(pow(X.first - Y.first, 2) + pow(X.second - Y.second, 2));
}
 
double travel(int i, int j) {
    if (DP[i][j] >= 0)
        return DP[i][j];
    if (i == N - 1)
        return DP[i][j] = distance(planet[j], planet[N - 1]);
    if (j == N - 1)
        return DP[i][j] = distance(planet[i], planet[N - 1]);
    int next = max(i, j) + 1;
    return DP[i][j] = min(travel(next, j) + distance(planet[i], planet[next]),
        travel(i, next) + distance(planet[j], planet[next]));
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> T;
    while (T--) {
        cin >> N;
        int x, y;
        for (int i = 0; i < N; i++) {
            cin >> x >> y;
            planet.push_back({ x,y });
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++)
                DP[i][j] = -1;
        }
        cout << travel(0, 0) << "\n";
        planet.clear();
    }
    return 0;
}

알고리즘 하시는 분들은 전부 대단하신 것 같다.