[DP] 백준 1757번 - 달려달려

 

 

DP를 안 쓴다면)

매분 달릴지 말지를 결정하는 완전 탐색을 진행해야 한다.

2^N이 되는데 

N<=10000을 고려하면 굉장히 큰수이다.

 

최적해를 구하고, 앞으로 쭈욱 나아가는 방향성, 상태가 존재 -> DP?

 

DP를 쓴다면)

상태 3가지 존재 

1. 몇분

2. 지침 지수

3. 달리는 상태

 

dis[n] -> 각 시간에서의 갈 수 있는 거리

dp[x][y][z] -> '최대한 갈 수 있는 거리'로 dp를 설정

x : 분

y : 지침 지수

z : 달리는 상태 (1:달림 0:쉼)

 

M은 2라고 가정

 

지침지수 0인 경우 y=0)

  dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1], dp[x-1][y][0] )

  

지침지수 1인 경우 y=1)

  dp[x][y][0] = max( dp[x-1][y+1][0], dp[x-1][y+1][1] )

        y-1에서 값을 가져올 수 없는 이유 >> y-1에서 뛴경우 안뛴 경우 모두 현재 x에서는 쉬기 때문에 y-2로 바뀌기 때문에 y가 될 수 없다 -> 고려할 필요가 없다

  dp[x][y][1] = max(dp[x-1][y-1][0], dp[x-1][y-1][1] ) + dis[x]

         y+1에서 값을 가져올 수 없는 이유 >> y+1에서 뛴 경우와 안뛴 경우 모두 현재 x에 와서는 뛰는 상태이므로 y+2로 올라가기 때문에 고려하지 않아도 된다

 

지침지수 2이상인 경우 y>=2)

  dp[x][y][0] = max( dp[x-1][y+1][1], dp[x-1][y+1][0])

  dp[x][y][1] = dp[x-1][y-1][1] + dis[x]

 

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
#define endl '\n'
#define DIV 1000000009

int dis[1000];
int dp[10000][10000][10000]; //시간, 지침지수, 달리는지 유무
int N, M;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int input;

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> input;
        dis[i] = input;
    }
    int x, y, z;
    for (int x = 0; x <= N; x++)
    {
        for (int y = 0; y <= N; y++)
        {
            if (y == 0)
            {
                dp[x][y][0] = max({dp[x - 1][y + 1][1], dp[x - 1][y + 1][0], dp[x - 1][y][0]});
            }
            else if (y == 1)
            {
                dp[x][y][1] = max(dp[x - 1][y - 1][1], dp[x - 1][y - 1][0]) + dis[x]; 
                dp[x][y][0] = max(dp[x-1][y+1][0], dp[x-1][y+1][1]);
            }
            else
            {
                dp[x][y][1] = dp[x-1][y-1][1]+dis[x];
                dp[x][y][0] = max(dp[x-1][y+1][1], dp[x-1][y+1][0]);
            }
        }
    }
    cout<<dp[N][0][0];
}