[BOJ/백준][Gold4] 2253 : 점프 (C++)

https://www.acmicpc.net/problem/2253

2253번: 점프

 

 

[난이도] Gold4
[유형] DP

[풀이]
DP[n][k] : n = 현재 돌의 번호, k = 이전에 점프한 칸의 개수
k는 최악의 겨우에도
1+2+3+4+...k=10000
이므로 (k+1)k/2 = 10000 의 식을 이용하면 대략 500은 절대 넘지 않으므로
배열을 DP[10000][500] 으로 설정하여 메모리 초과를 피하였씁니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,dp[10001][500],a[10000],inf=9e8;
int sol(int n,int k){
    if(n==N) return 0;
    if(n>N||a[n]) return -1;

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

    ret=inf;
    for(int i=k-1;i<=k+1;i++){
        if(i<1) continue;
        int v = sol(n+i,i);
        if(v==-1) continue;
        ret=min(ret,v);
    }
    if(ret==inf) return ret=-1;
    ret++;
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    while(M--){
        int v;
        scanf("%d",&v);
        a[v]=1;
    }
    memset(dp,-1,sizeof(dp));
    int ans = sol(2,1);
    if(ans==-1) puts("-1");
    else printf("%d",ans+1);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2253.cpp