공룡점프 (JUNGOL 12203)

https://jungol.co.kr/problem/12203?cursor=NTA4LDEsNg==

---

아이디어

dp[i][j]를 i번째칸에 도달하기 직전이고 그때까지의 j개의 아이템을 먹었을때의 걸리는 최소 시간이라고 정의합시다. 그러면 dp[i][j]와 i번째 칸에 아이템이 있는지의 여부를 바탕으로 dp테이블을 채워줄 수 있습니다. 만약 도착점이 N을 넘어선다면, 그때까지의 시간을 기록하여 마지막에 최솟값을 구해주면 됩니다.

---

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll dp[5050][5050]={0};

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N,i,j;
    string grid;

    cin>>N>>grid; 
    grid="?"+grid; //1-idx로 바꾸기

    for (i=1;i<=N;i++)
        for (j=0;j<=N;j++)
            dp[i][j]=1e18;
    dp[1][0]=0;
    
    ll res=1e18;
    for (i=1;i<=N;i++)
    {
        if (grid[i]=='#') continue;

        ll item=0;
        if (grid[i]=='*') item=1;

        for (j=0;j<=N;j++)
        {
            if (dp[i][j]==1e18) continue;
            dp[i+1][j+item]=min(dp[i+1][j+item],dp[i][j]+1);
            if (i+j+item+1>N) res=min(res,dp[i][j]+1);
            else dp[i+j+item+1][j+item]=min(dp[i+j+item+1][j+item],dp[i][j]+1);

            //cout<<"dp["<<i<<"]["<<j<<"] = "<<dp[i][j]<<"\n";
        }
    }

    if (res==1e18) cout<<-1;
    else cout<<res;
}