[ 백준 / 10653 번 ] Gold V - 마라톤2 : Solved By Ja

www.acmicpc.net/problem/10653

10653번: 마라톤 2

문제

농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.

마라톤 코스는 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 개를 건너뛰고 달릴 수 있는 최소 거리를 출력하라.

예제 입력 1 복사

5 2 0 0 8 3 1 1 10 -5 2 2

예제 출력 1 복사

4

힌트

젖소 박승원이 2번째 와 4번째 체크포인트를 건너뛸경우 경로는 (0,0) -> (1,1) -> (2,2) 로 4가 된다. 이보다 더 짧게 달릴수는 없다.

 

다이나믹 프로그래밍 문제 푸는 게 너무 약해서 

앞으로 DP위주로 연습을 해야겠다. 

 

풀이 코드 

package newProject;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 마라톤2 {
	static int arr[][],N,K, memo[][];
	public static void main(String[] args) throws IOException {
		BufferedReader br= new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		int [][]a = new int[N+1][2];
		for(int i =1; i<= N; i++) {
			st = new StringTokenizer(br.readLine());
			a[i][0]= Integer.parseInt(st.nextToken());
			a[i][1]= Integer.parseInt(st.nextToken());
		}
		arr = new int[N+1][N+1];
		for(int i =1; i< N;i++) {
			for(int j =i+1; j<= N; j++) {
				arr[i][j] = Math.abs(a[i][0]-a[j][0])+Math.abs(a[i][1]-a[j][1]);
			}
		}
		memo = new int[N+1][K+1];
		System.out.println(check(N,K));
	}
	private static int check(int n,int k) {
		if(memo[n][k]!=0)return memo[n][k];
		if(n==1) return 0;
		memo[n][k] = Integer.MAX_VALUE;
		for(int i = 0; i<= k; i++) {
			if(0<n-i-1) memo[n][k] = Math.min(check(n-i-1,k-i)+arr[n-i-1][n],memo[n][k] );
		}
		return memo[n][k];
	}
}

우선 27번까지는 모두 데이터 입력 부라고 보면 된다. DP를 사용하기때문에 별 다를 게 없다. 

 

1~N까지를 이용하도록 배열을 만들어서 그 Manhatan거리를 arr에 넣어 주었다.

그리고 제일 중요한 DP를 저장할 memo라는 배열을 동일하게 N+1* N+1크기로 정해주었다. 

그리고 chekc(N, K)를 출력하면 끝!

 

이지만 Check안에 DP과정이 들어가게 된다. DP는 점화식이라고 생각하면 되는데, 이전 값을 저장해두고 비교해서 넣는 것이다. 

처음에 들어온 값이 check(5,2)가 들어오게 된다.

memo는 초깃값으로 모두 0으로 초기화 되어 있다. 먼저, memo[5][2]값이 초기화 되어 있는지를 살펴본다. 

처음 값인 0이 아니라면 이미 계산 과정을 지났다는 의미이므로 탈출한다. 

또한 만약 n이 1이라면 이 값을 시작점을 의미하므로 0을 return 한다. 

 

이 두경우가 아닌 memo[5][2]부터 살펴보면, 

먼저 memo[5][2]를 최대값으로 정해준다. 그리고 반복문을 돌면서 가장 작은 값으로 바꾸어 return하게 된다.

반복문을 i를 0~k까지 돌게 되는데, k가 건너뛸 수 있는 개수를 말한다. 현재, n=5, k=2이므로, 최대 두개 까지 건너 뛸 수 있다. 

그렇다면 계산 과정을 본다. 

memo[n][k]에 memo[n-1-i][k-i] + arr[n-1-i][n] 과 memo[n][k]를 비교해서 더 작은 값을 넣어주어야 한다. 

먼저 i=0일 때, 건너뛰지 않는 다는 것을 의미한다. 

memo[5][2] 와  memo[4][2] + arr[4][5]  으로 

memo[4][2]는 1~4번 까지 오는 2칸 뛰기한 최소값 , + arr[4][5]: 4->5번까지 걸리는 거리 

 

그리고 i=1일 떄는 한칸을 건너뛴다는 의미이다. 

memo[5][2]와 memo[3][1] + arr[3][5] 를 비교한다. 

3까지 한번 건너뛰오 온 최소값과 arr[3][5]로 3->5로 가는 거리를 계산한다. 

i=2 = k일 떄는 

memo[5][2]와 memo[2][0] + arr[2][5]로 한번에 두칸 모두 건너뛴 경우까지 고려하여 계산한다. 

 

이 떄 memo[4][2]를 부를 때 check(4,2)로 계산과정에 한번 더 들어가는 재귀를 사용하게 되는데, 

같은 방법으로 

memo[4][2]와  memo[3][2] + arr[3][4] 를 비교하고, 

memo[4][2]와 memo[2][1] + arr[2][4], 

memo[4][2]와 memo[1][0] + arr[1][4]를 비교하여 최소값을 넣는다.  // 

여기에서 memo[1][0] 은 시작점이므로 이미 0을 리턴하게 되고, 그 다음 arr[1][4]만 으로 비교하게된다. 

이러한 재귀과정 중에 이미 한번 계산 된 값이 있을 수 있으니, 

memo[n][k]!=0이 아닌 경우 이미 계산이 완료되어 최소값이 들어있다는의미이므로 memo[n][k]를 바로 return해준다. 

 

나는 DP가 참 어렵다.... 머릿속에서 이 계산이 안나온다... 

 

앞으로 이 방법을 써서 잘 해보자... 

 

marathon_silver.zip

0.02MB

 

 

그리고 위에 이건 테스트 케이스 이다.