2253

위 문제는 가속/감속을 최대 1 만큼 한다는 것에 힌트가 있다.

돌의 개수가 최대 10000개 일 때 최대로 낼 수 있는 속도는 142이다. K*(K+1)/2 < 10000

현재 위치의 돌과 돌에 도착할 때의 속도로 새롭게 정점을 표현한다면 최대 정점의 개수는 10000 * 142 로 배열 내에서 선언이 가능한 범위가 된다.

dp[N][V] : N번째 돌에 V번째 속도로 도착할 때의 최소 점프횟수

이제 각각의 정점을 방문해서 다음 위치에 움직일 때 최소 횟수로 움직이는 값을 업데이트 해주면 된다.

 
#include<cstdio>

#define MAXN 10000

int dp[MAXN + 5][200];
int forbid[MAXN];

int main() {
	int N, M;
	int i, j, tmp;

	int ans;

	freopen("input.txt", "r", stdin);
	scanf("%d%d", &N, &M);

	while (M--) {
		scanf("%d", &tmp);
		forbid[tmp] = 1;
	}

	dp[1][0] = 1;

	for (i = 1; i <= N; i++) {
		if (forbid[i])
			continue;
		for (j = 0; j < 200; j++) {
			if (dp[i][j]) {
				if (i + j <= N) {
					if (dp[i + j][j] == 0 || dp[i + j][j] > dp[i][j] + 1)
						dp[i + j][j] = dp[i][j] + 1;
				}
				if (i + j + 1 <= N) {
					if (dp[i + j + 1][j + 1] == 0 || dp[i + j + 1][j + 1] > dp[i][j] + 1)
						dp[i + j + 1][j + 1] = dp[i][j] + 1;
				}
				if (j - 1 > 0 && i + j - 1 <= N) {
					if (dp[i + j - 1][j - 1] == 0 || dp[i + j - 1][j - 1] > dp[i][j] + 1)
						dp[i + j - 1][j - 1] = dp[i][j] + 1;
				}
			}
		}
	}

	ans = 0;

	for (i = 0; i < 200; i++) {
		if (dp[N][i] != 0)
			if(ans == 0 || ans!=0 && dp[N][i] < ans)
				ans = dp[N][i];
	}
		
	printf("%d\n", ans - 1);

	return 0;

}

문제에서 제시한 정점에서 벗어나 새로운 정점을 만들어주는 방식이 중요하다. DP문제를 풀 때는 위 방식이 핵심이다.