[BOJ/백준][Gold4] 1757 : 달려달려 (C++)

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

1757번: 달려달려

 

 

[난이도] Gold4
[유형] DP

[풀이]
2차원 DP 문제 입니다.

DP[n][m] : 현재 지침 지수가 m이고 n분일 N-1분까지 달릴 수 있는 최대 거리

점화식은 n번 분에서 뛰거나 뛰지 않는 경우로 나누어서 생각할 수 있습니다.

Top-Down DP를 사용하였기 때문에 sol(n,m) 은 DP[n][m]을 구하고 return 합니다.

case 1) 뛰는 경우
    뛰면 m 값이 1증가 해야 하는데 만약 m+1>M이 된다면 문제의 조건에 의해 더이상 뛸 수 없으므로
    뛰어서는 안됩니다.
    m+1<=M 이라면 sol(n,m) = sol(n+1,m+1)+a[n] 이 됩니다.

case 2) 뛰지 않는 경우
    m>0 이라면 문제의 조건에 의해 m이 0이 될 때까지 쉬어야 하고
    적어도 마지막 분까지 쉬었을 때 m이 0이 되어야 하므로 n+m<=N 인 경우에만
    sol(n,m) = sol(n+m,0) 이 됩니다. (m은 다 쉬었기 때문에 0이 됨)

    만약 m==0 이라면 m값은 변화 없이 sol(n,m) = sol(n+1,0) 이 됩니다.

위의 값들 중 최댓값을 최종 sol(n,m)의 값으로 return 해야 합니다.

종료 조건 (n==N)
    n==N일 때 m은 0이어야 하므로 0이 아니라면 아주 큰 음수 inf를 return하여 최종 답에서 무시되도록 합니다.

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int N,M,dp[10001][502],a[10001],inf=-9e8;
int sol(int n,int m){
    if(n==N) {
        if(m==0) return 0;
        return inf;
    }
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret=inf;
    if(m>0) {
        if(n+m<=N) ret=max(ret,sol(n+m,0));
    }else {
        ret=max(ret,sol(n+1,0));
    }

    if(m+1<=M) ret=max(ret,sol(n+1,m+1)+a[n]);
    return ret;
}
int main(){
    scanf("%d%d",&N,&M);
    for(int i=0;i<N;i++) scanf("%d",&a[i]);
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(0,0));
}

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