백준 1757 (달려달려)

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

1757번: 달려달려

달리기 하다가 N분 지났을 때 조건을 만족하면서 갈 수 있는 최대거리

 

조건은 다음과 같다.

 

체력 한계 초과 불가

끝날 때 체력 풀 

쉬기 시작하면 체력 풀 될때까지 쉬어야 한다.

 

이 문제가 dp인건 먼저 알고 풀었다. 그러면 dp라고 생각할 수 있게 만드는 것들이 뭐가 있는지 생각해보자 

 

완전탐색요소가 존재한다. 

모든 단계에서 할 수 있는건 그 전 단계에서 온 상태에서의 뛴다 or 안 뛴다. 

 

결국 구하려고 하는 최대 거리는 그 전 단계에서의 최대거리에서 온다. 

그러니깐 똑같은 조건이면 무조건 최대거리인게 좋다 

뒤에 영향을 주는 그래프가 아니기 때문에

 

DAG이다. 

 

뭐 했던 말 또하는 말들이기는 한데 위 상황들 때문에 dp라고 생각할 수 있는 것 같다. 

 

 

다시 문제로 돌아가면 

 

i 시간에 dp값을 구할건데 

그 시간에 지침지수가 존재한다.

 

그냥 이렇게 이차원 dp를 하게된다면 

위 조건 쉬기 시작하면 체력 풀 

조건을 위반하게 된다.

 

왜냐하면 그전에 쉬었는지 안 쉬었는지 알수있는 방법이 없기 때문에 

 

따라서 삼차원 dp로 

i시간, 지침지수, 달림유무로 dp테이블을 구성하고 구현하면 된다.

 

 

 

달린다면 지침지수 + 1,  + 해당 이동 거리 

 

max ( 그전에 안 달렸을 때 -> 지침지수 0일때만 사용 가능 3번 조건때문에 

그전에 달렸을 때 )

 

안 달린다면 지침지수 -1

 

max ( 그 전에 안 달렸을 때 

그 전에 달렸을 때 )

 

이렇게 구현하면 된다.

 

#include <bits/stdc++.h>

using namespace std;
#define TEST int tt; cin >> tt; while (tt--)
#define all(v) (v).begin(), (v).end()
#define loop(e, v) for (auto& (e) : (v))
#define mem(v, e) memset((v), (e), sizeof(v))
#define _unique(v) (v).erase(unique((v).begin(),(v).end()),(v).end())
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tii tuple<int, int, int>
#define tll tuple<ll, ll, ll>
#define xx first
#define yy second
#define ll long long
#define ld long double
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(0);
const int MAX = 1005;
const int INF = 1e9 + 1;
const ll LINF = 1e18;
const ll MOD = 1e9 + 7;

int dp[10005][505][2];
int num[10005];

int main() {
    FASTIO
    int N, M;
    cin >> N >> M;
    for(int i=0; i<N; i++)cin >> num[i]; 

    dp[0][1][1] = num[0];
    for(int i=1; i<N; i++){
        for(int j=0; j<=M; j++){
            dp[i][j][0] = max({dp[i-1][j][0], dp[i-1][j+1][1], dp[i-1][j+1][0]});
            if(j>0){
                dp[i][j][1] = dp[i-1][j-1][1] + num[i];
                if(j==1) dp[i][j][1] = max({dp[i][j][1], dp[i-1][0][0] + num[i]});
            }
        }
    }
//    for(int i=0; i<N; i++){
//        for(int j= 0; j<=M; j++){
//            cout << dp[i][j][0] << " " << dp[i][j][1] << "  ";
//        }
//        cout <<'\n';
//    }
    cout << dp[N-1][0][0];
}