[백준 1757번] [동적 계획법] 달려달려

문제 자체는 그렇게 어렵지 않다.

 

i번째에서 거리는 사실상 i-1번째의 상태에 의해서 결정되는 양상으로 진행된다.

 

추가적으로 조건을 잘 살펴보면 i분째 상태는 지침지수와 운동상태인지/쉬는 상태인지 여부에 따라 결정된다.

따라서 이러한 측면에서 

3차원 DP가 필요하게 된다.

 

dp[i][j][k] = i번째 분이 지났을 때 지침 지수가 j일때 달린 거리(단, k가 0이면 i번째 분일 때 쉰 상태, 1이면 달린 상태)

 

그리고 조건을 활용해서 점화식을 잘 세우면 다음과 같다.

(단, d[i]는 i번째분에서 달릴 경우 갈 수 있는 거리)

 

1) 현재 움직히고 있는 상황인 경우(k가 1)

dp[i][j][1] = dp[i - 1]j - 1][1] + d[i]가 기본적인 상황이다.

단, 만약 j가 1인 경우에는 dp[i][1][1] = dp[i - 1][0][0]이다.

 

2) 현재 멈춰 있는 상황

dp[i][j]0] = max(dp[i - 1][j + 1][0], dp[i][j + 1][1])

 

단, 만약 j가 M - 1인 경우

dp[i][M - 1][0] = dp[i - 1][M][1]이다.

 

또한 j가 0인 경우

dp[i][j][0] = max(max(dp[i - 1][j + 1][0], dp[i][j + 1][1]), dp[i - 1][j][0)이다.

왜냐하면 이전 상태에서 지침지수가 0인 경우 지침지수가 유지되기 때문이다.

 

해당하는 논리로 DP를 Recursion을 활용해서 구하였다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;

using namespace std;

int dp[10001][501][2];
int d[10001];

int N, M;

int dp_check(int i, int j, int k){
    if(i == 0) return dp[i][j][k];
    if(k == 1){
        if(j == 1){
            if(dp[i - 1][0][0] == -1){
                dp_check(i - 1, 0, 0);
            }
            return dp[i][j][k] = dp[i - 1][0][0] + d[i];
        }
        if(dp[i - 1][j - 1][1] == -1){
            dp_check(i - 1, j - 1, 1);
        }
        return dp[i][j][k] = dp[i - 1][j - 1][k] + d[i];
    }
    else{
        if(j == M - 1){
            if(dp[i - 1][M][1] == -1){
                dp_check(i - 1, M, 1);
            }
            if(j == 0){
                if(dp[i - 1][j][0] == -1){
                    dp_check(i - 1, j, 0);
                }
            }
            return dp[i][j][0] = max(dp[i - 1][M][1], dp[i - 1][j][0]);
        }
        if(dp[i - 1][j + 1][0] == -1){
            dp_check(i - 1, j + 1, 0);
        }
        if(dp[i - 1][j + 1][1] == -1){
            dp_check(i - 1, j + 1, 1);
        }
        if(j == 0){
            if(dp[i - 1][j][0] == -1){
                dp_check(i - 1, j, 0);
            }
            return dp[i][j][k] = max(max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]), dp[i - 1][j][k]);
        }
        return dp[i][j][0] = max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]);
    }
}

int main(void){
    memset(dp, -1, sizeof(dp));
    memset(d, -1, sizeof(d));

    cin >> N >> M;

    for(int i = 1; i <= N; i++){
        int temp;
        cin >> temp;
        d[i] = temp;
    }
    dp[1][1][1] = d[1];
    dp[1][0][0] = 0;

    cout << dp_check(N, 0, 0) << "\n";
    int n;

    return 0;
}

예외처리 조건이 많아서 좀 골치아프다.

그런데 잘 생각해보면 예외처리 조건이 많은 이유는 index가 범위를 넘냐 안넘냐에 대한 문제과 관련이 깊다.

근데 만약 dp의 default value를 0으로 설정해주면 쉽게 해결할 수 있다.

 

예를 들어 멈춰있는 상황에서 j가 M - 1일때를 굳이 따로 체크해준 본질적인 이유가

dp[i - 1][M][0]이 존재할 수 없기 떄문이다.

그런데 0으로 초기화준 상태에서는 그냥 더해줘도 나오는 값에는 차이가 존재하지 않는다.

 

추가적으로 재귀보다는 반복분으로 처리하는 편이 더 좋아보인다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <queue>
typedef long long ll;

using namespace std;

int dp[10001][501][2];
int d[10001];

int N, M;

int main(void){
    memset(dp, 0, sizeof(dp));
    memset(d, 0, sizeof(d));

    cin >> N >> M;

    for(int i = 1; i <= N; i++){
        int temp;
        cin >> temp;
        d[i] = temp;
    }
    dp[1][1][1] = d[1];
    dp[1][0][0] = 0;

    for(int i = 2; i <= N; i ++){
        for(int j = 0; j <= M; j++){
            if(j != 1){
                if(j != 0){
                    dp[i][j][1] = dp[i - 1][j -1][1] + d[i];
                    dp[i][j][0] = max(dp[i - 1][j + 1][1], dp[i -1][j + 1][0]);
                }
                else{
                    dp[i][j][0] = max(max(dp[i - 1][j + 1][0], dp[i - 1][j + 1][1]), dp[i - 1][j][0]);
                }
            }
            else{
                dp[i][j][1] = max(dp[i -1][j -1][1], dp[i -1][j -1][0]) +d[i];
                dp[i][j][0] = max(dp[i - 1][j + 1][1], dp[i - 1][j + 1][0]);
            }
        }
    }
    cout << dp[N][0][0] << "\n";
    return 0;
}

맨 위 코드가 맨 처음 짠 코드이다. 왔다갔다해서 비효율적이다.