오늘 푼 문제는 매일 코딩 저장소에서 랜덤 숫자 생성으로 고른 백준 10653 마라톤2이다.
골드 4 문제인데, 풀고나니 간단한 문제인데 엄청 고생했다 ㅜㅜ 그게 어려운거겟지.. 풀고나면 다 쉬운 문제가 되는 거겟지..
문제
농장에 있는 젖소들이 건강하지 못하다고 생각한 농부 존은 젖소들을 위한 마라톤 대회를 열었고, 농부 존의 총애를 받는 젖소 박승원 역시 이 대회에 참가할 예정이다.
마라톤 코스는 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풀이 방법
사실 비슷한 류의 문제를 몇 번 풀어봤다. 이 중 최대/최소 몇 개만 선택해서 가장 작은/큰 수를 만들어라 그런 류..
풀이 방법의 결론만을 말하면 dp로 해결했고, dp[k][n]에 저장되는 값은 n번째 좌표에 도착했을 때, 그 전까지 k개를 건너뛴 경우에 최소 거리가 저장되는 것이다. dp라하면 단순 무슨 값을 저장하는가가 아니라 이미 저장된 값들을 어떻게 이용해서 계산을 줄일 것이냐가 나와야 할 것이다. 만일 2번 건너뛰어서 지금의 n번째 좌표에 도착한 경우의 최소 값을 구하고 싶다면, 아래의 세 가지 경우가 있으니 각 값을 구하고 그 중 최소 값을 저장하면 되는 것이다.
-
n-1번째에서 2번을 건너뛴 경우의 최소 값 + n-1과 n 사이의 거리
이미 n-1까지 두 번 건너뛰고( n-1 이전까지 좌표중 어떤 좌표를 건너뛴지 모르지만 모든 경우 중 최소값이 저장되어 있는 것이다 ), n-1은 건너뛰지 않은 값이 구해져 있는 것이니 이전 좌표부터 현재까지의 거리만 더해준다.
-
n-2번째에서 1번을 건너뛴 경우의 최소 값 + n-2와 n 사이의 거리
이미 n-2까지 한 번 건너뛰고( n-2 이전까지 좌표중 어떤 좌표를 건너뛴지 모르지만 모든 경우 중 최소값이 저장되어 있는 것이다. ), n-2는 건너뛰지 않은 값이 구해져 있는 것이고, 지금 2번 건너뛴 경우를 구하고 있는 것이니 n-1을 건너뛰어야만 하므로 n-2부터 현 좌표까지 거리만 더해준다.
-
n-3번째에서 0번을 건너뛴 경우의 최소 값 + n-3과 n 사이의 거리
이미 n-3까지 한 번도 건너뛰지 않은 값이 구해져 있는 것이고, 지금 2번 건너뛴 경우를 구하고 있는 것이니 n-1, n-2를 건너뛰어야만 하므로 n-3부터 현 좌표까지 거리만 더해준다.
위의 내용들을 토대로 점화식을 표현할 수 있을 것이다.
dp[k][n] = 0<=i<=k 일 때, dp[k-i][n-i-1] + distance(n-i-1, n)들 중 최소값또한 세번째 좌표에 대한 값을 구하는데 이미 2번 건너뛴 경우는 불가능하므로 계산할 필요가 없으므로 조건을 통해서 연산을 생략하고 초기 값인 -1로 두고, 이후에 다음 dp들을 구할 때도 이용하는 값이 -1인지를 판별하여 불필요한 연산을 줄일 수 있다
풀고나니 간단한 문젠데 사실 고생을 좀 했다.. 무슨 세시간은 붙잡고 있었다 😤 그리고 그저께 푼 문제인데 이제서야 포스팅을 하고 있다.. 에휴 무기력한 요즘이다 ! 사실 그래서 글도 대충 쓰게 된 것 같다 하지만 풀이법은 확실히 파악하고 있으니 혹 이 글을 읽으셨으나 잘 모르겠는 분들은 댓글 남겨주세옹..
코드
import java.io.*;
import java.util.*;
public class Main {
static int[][] distance;
static Point[] points;
public static class Point{
private int x;
private int y;
Point(int x, int y){
this.x = x;
this.y = y;
}
}
public static int calculateDistance(int a, int b){
if(distance[a][b] == -1) {
int dis = Math.abs(points[a].x-points[b].x) + Math.abs(points[a].y-points[b].y);
distance[a][b] = dis;
distance[b][a] = dis;
}
return distance[a][b];
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // reader
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // writer
StringTokenizer st; // tokenizer
st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
points = new Point[n];
int[][] dp = new int[k+1][n];
distance = new int[n][n];
int[] arr;
for(int i=0; i<n; i++){
st = new StringTokenizer(br.readLine());
points[i] = new Point(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
arr = new int[n];
Arrays.fill(arr, -1);
distance[i] = arr;
}
for(int i=0; i<=k; i++) {
arr = new int[n];
Arrays.fill(arr, -1);
dp[i] = arr;
if(i==0) dp[i][0] = 0;
}
int min, temp;
for(int i=1; i<n; i++){
for(int j=0; j<=k; j++){
if(i-j > 0){
min = Integer.MAX_VALUE;
for(int z=0; z<=j; z++){
temp = dp[j-z][i-z-1];
if(temp == -1) continue;
min = Math.min(min, temp+calculateDistance(i-z-1, i));
}
dp[j][i] = min;
}
}
}
int result = dp[0][n-1];
for(int i=1; i<=k; i++){
if(dp[i][n-1] < result) result = dp[i][n-1];
}
bw.write(String.valueOf(result));
bw.write( "\n"); // for return value
bw.flush(); // flush
bw.close(); // close
br.close(); // close
}
}