[SWEA] 9092 마라톤

출처: SWEA

 Input 

2

5 2

0 0

8 3

1 1

10 -5

2 2

5 3

0 0

8 3

1 1

10 -5

2 2

 

 Output 

#1 4

#2 4

 

▶ dp[cur][k] = min(dp[cur][k], solve(next, k - i) + distance(cur, next));

dp[현재위치][남은 점프 수] → 가능한 건너뛰기를 고려해서 갈수 있는 칸으로 뛰어본다.

---

#include <iostream>
#include <vector>
#include <string.h>
#define MAX 123456789
using namespace std;
int dp[501][501];
vector<pair<int, int>> v;
int N, K, x, y;
 
int abs(int x) {
    return x >= 0 ? x : -x;
}
 
int min(int x, int y) {
    return x < y ? x : y;
}
 
int distance(int A, int B){
    return abs(v[A].first - v[B].first) + abs(v[A].second - v[B].second);
}
 
int solve(int cur, int k){
    // 도착한 경우
    if (cur == N - 1) return 0;
    
    // 이미 지나간 경우
    if (dp[cur][k] != -1) return dp[cur][k];
 
    dp[cur][k] = MAX;
 
    for (int i = 0; i <= K; i++) {
        int next = cur + i + 1;
        if (next > N - 1) continue;
        if (k - i < 0) continue;
        
        dp[cur][k] = min(dp[cur][k], solve(next, k - i) + distance(cur, next));
    }
 
    return dp[cur][k];
}
 
int main() {
    int testCase; cin >> testCase;
    for (int tc = 1; tc <= testCase; ++tc) {
        cin >> N >> K;
        v.clear();
        memset(dp, -1, sizeof(dp));
        for (int i = 0; i < N; i++) {
            cin >> x >> y;
            v.push_back(make_pair(x, y));
        }
        // 정답 출력
        printf("#%d %d\n", tc, solve(0, K));
    }
}