백준 10653(마라톤 2)

www.acmicpc.net/problem/10653

10653번: 마라톤 2

문제를 보자마자 재귀의 점화식이 떠오르긴 했다. 

 

근데 이게 dp인지는 알기가 힘들었다. dp가 뭔지 제대로 모르고 있어서 그런가 그래도 점화식을 바탕으로 dp라고 생각하고 풀었다. 처음에는 최대 K개를 계속해서 패스할 수 있다는 건줄 알고 그렇게 풀었으나 틀렸습니다.를 맞은 후에 알았다. 

 

재귀형식으로 돌아가는 구조와, 점화식 이 두개만 알면 구현도 쉬운 dp문제이다. 

 

 

dp[N][K]는 N체크포인트에서 K개의 건너 뜀을 행하였을때의 최소 값을 저장한다. 

 

N==1 이 될때까지 확인을 하고 그 중에 최솟값을 계속해서 저장해서 올라오는 방식인 것이다. 그냥 재귀함수의 구조

 

점화식은 따라서 dp[N][K] = min(dp[N-i-1][K-i]+ 택시거리)체크포인트 건너뜀을 최대 K개 까지 했을때로 구현하면 된다.

 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<cstring>
using namespace std;
#define MAX 505

int dis[MAX][MAX];
int dp[MAX][MAX];
int N, K;
vector<pair<int, int> > v;

int solve(int idx, int k) {
	if (idx == 1)return 0;
	if (dp[idx][k]!=-1) return dp[idx][k];

	int min_n = 987654321;
	for (int i = 0; i <= k; i++) {
		if (idx - i-1 < 1) break;
		min_n = min(solve(idx - i-1, k - i) + dis[idx-i-1][idx], min_n);
	}
	return dp[idx][k] = min_n;
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < N-1; i++) {
		for (int j = i+1; j <= N-1; j++) {
			dis[i+1][j+1] = abs(v[i].first - v[j].first) + abs(v[i].second - v[j].second);
		}
	}


	cout << solve(N, K) << '\n';
}