(C++) - 백준(BOJ) 10653번 : 마라톤 2 답

www.acmicpc.net/problem/10653

10653번: 마라톤 2

dp로 푼 문제였습니다.

 

풀이방법

d[n][k] : n번째 체크포인트를 선택했을 때 k개만큼 건너뛰었을 때의 최소 거리일 때 점화식은 다음과 같습니다.

0<=i<=k까지 매 loop마다 건너뛰는 좌표의 거리를 모두 확인합니다. 그 후

정답 : min(n-i-1번째 체크포인트를 선택했을때 k-i개만큼 건너뛴 상태에서 최소 거리 + n-i-1에서 n까지의 거리, d[n][k])

 

Code

#include <bits/stdc++.h>
using namespace std;
int n,k;
vector <pair<int,int>> v(1000);

int a[501][501];
int d[501][501];

int dp(int n,int k){
    int &ret = d[n][k];
    if(ret!=-1) return ret;
    if(n==1) return 0;

    ret = 0x7f7f7f7f;

    for(int i  = 0; i <= k; i++){
        if(1 <= n-i-1) ret = min(dp(n-i-1,k-i) + a[n-i-1][n],ret);
    }

    return ret;
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i ++){
        cin >> v[i].first >> v[i].second;
    }
    
    memset(d,-1,sizeof(d));
    for(int i = 1; i <= n-1; i++){
        for(int j = i+1; j <= n; j++){
            a[i][j] = abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second);
        }
    }

    cout << dp(n,k);
}