농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.
마라톤 코스는 N (3 <= N <= 500) 개의 체크포인트로 구성되어 있으며, 1번 체크포인트에서 시작해서 모든 체크 포인트를 순서대로 방문한 후 N번 체크포인트에서 끝나야지 마라톤이 끝난다. 게으른 젖소 박승원은 막상 대회에 참가하려 하니 귀찮아져서 중간에 있는 체크포인트 K 개를 몰래 건너뛰려 한다. (K < N) 단, 1번 체크포인트와 N번 체크포인트를 건너뛰면 너무 눈치가 보이니 두 체크포인트는 건너뛰지 않을 생각이다.
젖소 박승원이 체크포인트를 최대 K 개 건너뛰면서 달릴 수 있다면, 과연 승원이가 달려야 하는 최소 거리는 얼마일까?
참고로, 젖소 마라톤 대회는 서울시내 한복판에서 진행될 예정이기 때문에 거리는 택시 거리(Manhattan Distance)로 계산하려고 한다. 즉, (x1,y1)과 (x2,y2) 점 간의 거리는 |x1-x2| + |y1-y2| 로 표시할 수 있다. (|x|는 절댓값 기호다.)
첫 번째 줄에 체크포인트의 수 N과 건너뛸 체크포인트의 수 K가 주어진다.
이후 N개의 줄에 정수가 두개씩 주어진다. i번째 줄의 첫 번째 정수는 체크포인트 i의 x 좌표, 두 번째 정수는 y 좌표이다. (-1000 <= x <= 1000, -1000 <= y <= 1000)
체크 포인트의 좌표는 겹칠 수도 있다 - 젖소 박승원이 한 체크포인트를 건너뛸 때는 그 번호의 체크포인트만 건너뛰며, 그 점에 있는 모든 체크포인트를 건너뛰지 않는다.
젖소 박승원이 체크포인트 K 개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.
5 2
0 0
8 3
1 1
10 -5
2 2
4
이 문제는 DP(다이나믹 프로그래밍) 알고리즘을 이용해서 풀 수 있었는데 아직 DP가 익숙하지 않아서 풀기 어려웠다. 비교적 쉬운 DP 문제이기 때문에 더 많은 DP 문제를 풀면서 공부해야 할 것 같다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int[][] dp;
public static void main(String[] args) throws Exception{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] input = br.readLine().split(" ");
int N = Integer.parseInt(input[0]);
int K = Integer.parseInt(input[1]);
Pair[] arr = new Pair[N];
int[][] dist = new int[N][N];
dp = new int[N][K+1];
for(int i=0; i<N; i++) {
for(int j=0; j<=K; j++)
dp[i][j] = -1;
}
for(int i=0; i<N; i++) {
input = br.readLine().split(" ");
arr[i] = new Pair(Integer.parseInt(input[0]), Integer.parseInt(input[1]));
}
for(int i=0; i<N; i++) {
for(int j=i+1; j<N; j++) {
dist[i][j] = Math.abs(arr[i].x-arr[j].x) + Math.abs(arr[i].y-arr[j].y);
dist[j][i] = Math.abs(arr[i].x-arr[j].x) + Math.abs(arr[i].y-arr[j].y);
}
}
System.out.println(dfs(dist, N-1, K));
}
public static int dfs(int[][] dist, int idx, int k) {
if (idx == 0) return 0;
if (dp[idx][k]!=-1) return dp[idx][k];
int d = Integer.MAX_VALUE;
for (int i=0; i<=k; i++) {
if (idx-i-1 < 0) break;
d = Math.min(dfs(dist, idx-i-1, k-i) + dist[idx-i-1][idx], d);
}
return dp[idx][k] = d;
}
public static class Pair {
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
}
좋은 풀이 감사합니다. 근데 k의 값이 음수가 될 수 있어서 해당 부분을 고려해야 할 것 같습니다!