백준 10272 현상금 사냥꾼 김정은 C++풀이 - DP

 

 

x 좌표로 정렬된 행성 리스트가 주어지며,

행성을 이동할 때, 다음 행성은 항상 지금 행성보다 x 좌표가 커야 한다.

또한 전체 이동거리가 최소가 되도록 해야 하므로

Greedy 방식은 특정 케이스에만 맞을 수 있으므로 DP를 이용한다.

 

중요한 것은 x,y 좌표 사이에 맨해튼 거리를 구해야하므로 square root( delta x ^2 + delta y ^2 ) 을 구해야하고, 

소수점 2자리까지 맞아야하므로 double 형이나 float형을 써야 한다.

 

dp 배열은 3가지를 중심으로 생각한다.

1. dp배열 정의

2. 초기값

3. 점화식

 

dp 배열을 정의하는 것이 가장 중요하며,

생각하기 힘들기 때문에 DP 문제의 가장 어려운 부분인 것 같다.

하지만 정의되기만 한다면 2,3 은 (거의) 자동으로 정해진다.

 

dp를 떠올리는 방식은 brute force 가 가능하되 시간 최적화가 필요할 때이다.

 

dp를 짤 때 가장 중요한 것은, 말로 정의하는 것이다.

 

이 문제의 경우,

행성은 빠짐없이 들러야하므로 성립할 수 있는 방식인데, 

두 대의 우주선이

1번행성에서 동시에 출발하여 마지막 N 번째 행성까지 

차례대로 겹치지 않게 방문한다고 가정한다.

 

 

dp[i][j] 를

"1번 우주선이 i번째 행성에 가고, 2번 우주선이 j번째 행성에 갔을 때, 남은 행성을 방문할 최단 거리"

로 정의했다.

 

 

즉 dp[1][2] = min ( dp[3][2] + dist( 1->3) , dp[1][3] + dist(2->3)) 이 된다.

(dist(1->3)은 1번 행성에서 3번 행성으로 이동하는 거리를 뜻함)

 

이것은 1번 우주선이 1번 행성, 2번 우주선이 2번 행성에 있을 때, 남은 행성들의 총 최단 거리를 뜻하고,

1번 우주선이 3번 행성으로 갔을 때 최단 거리와

2번 우주선이 3번 행성으로 갔을 때의 최단거리를

비교해서 결정해야 한다.

 

이것을 일반화 하면 점화식은,

 

next = max(i,j)+1; //차례대로 방문

dp[i][j] = min(dp[next][j] + dist(i->next), dp[i][next] + dist(j->next))

 

로 만들 수 있다.

 

이제 2번 초기값을 생각해보면,

두 대의 우주선은 1번 행성에서 출발하므로 dp[1][1] 이 최단경로 거리를 저장할 것이다.(재귀를 통한 top-bottom방식)

또한 어느 한 우주선이 N에 도착했을 경우, 다른 우주선도 곧장 N번 행성으로 오면 되므로(남은 행성이 없음)

i, j 중 하나가 N이면 둘 중 N번 행성이 아닌 우주선이 N번 행성으로 오는 거리를 반환하면 된다.( dist(i ->N) )

#include <cstdio>
#include <math.h>
#include <algorithm>
#include <cstring>
using namespace std;
#define INF 987654321
int N, T, x, y;

struct st {
	int x, y;
};
st co[513];
double dp[515][515];

double dist(int x1, int y1, int x2, int y2) {
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));//return double
}
//우주선 두 갤 이용해서 가장 오른쪽에 도착하기
//dp[첫번째우주선 행성 위치인덱스][두번째 우주선 인덱스]
//dp[0][1] 시작해서 가장 최단거리 = min(dp[0][2] + dist(s2,arr[2]), dp[2][1]+dist(s1,arr[2]);
//dp[N][i] 도착시 i->N 으로 보내야함
double makedp(int s1,int s2) {
	if (s1 == N) {
		return dist(co[s2].x, co[s2].y, co[N].x, co[N].y);
	}
	else if (s2 == N) {
		return dist(co[s1].x, co[s1].y, co[N].x, co[N].y);
	}
	if (dp[s1][s2]) return dp[s1][s2];
	int next = max(s1, s2) + 1;
	//2번이 간 꼉우
	double p = makedp(s1, next) + dist(co[s2].x, co[s2].y, co[next].x, co[next].y);
	//1번이 간 경우
	double q = makedp(next, s2) + dist(co[s1].x, co[s1].y, co[next].x, co[next].y);
	
	return dp[s1][s2]=min(p, q);
}

int main() {
	scanf("%d", &T);
	for (int loop = 1; loop <= T; loop++) {
		scanf("%d", &N);
		memset(dp, 0, sizeof(dp));
		for (int i = 1; i <= N; i++) {
			scanf("%d %d", &x, &y);
			co[i].x = x;
			co[i].y = y;
		}
		makedp(1, 1);
		printf("%lf\n", dp[1][1]);
	}
}