[SWEA][9092번] 마라톤

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Opy-KWPoDFAWY

SW Expert Academy

 

풀이과정

1. 완전탐색으로 풀었다가 시간초과가 나서 Dp로 변경

 

2. 최대 K만큼의 구간을 건너 뛸 수 있으므로 dp[N][K]로 dp 사이즈 결정

 

3. dp[cur][K] = dp[next][K] + dis(cur, next) 와 같은 식을 구할 수 있다.

 

소스코드

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#define MAX_VAL 0x7fffffff
using namespace std;
int dp[501][501];
vector<pair<int, int>> v;
int N, K;
int abs(int n) {
	return n >= 0 ? n : n * -1;
}

int calcDis(int n1, int n2)
{
	int tmp = abs(v[n1].first - v[n2].first) + abs(v[n1].second - v[n2].second);
	return tmp;
}

int solution(int cur, int k)
{
	if (cur == N - 1) return 0;
	if (dp[cur][k] != -1) return dp[cur][k];

	dp[cur][k] = MAX_VAL;
	for (int i = 0; i <= K; i++) {
		int next = cur + i + 1;
		if (next > N - 1) continue;
		if (k - i < 0) continue;
		int dis = calcDis(cur, next);
		dp[cur][k] = min(dp[cur][k], dis + solution(next, k - i));
	}
	return dp[cur][k];
}

int main()
{
	int tc;
	scanf(" %d", &tc);
	for (int t = 1; t <= tc; t++) {
		scanf(" %d %d", &N, &K);
		v.clear();
		memset(dp, -1, sizeof(dp));
		for (int i = 0; i < N; i++) {
			int x, y;
			scanf(" %d %d", &x, &y);
			v.push_back(make_pair(x, y));
		}
		printf("#%d %d\n", t, solution(0, K));
	}
}