[BOJ22869 징검다리 건너기(small)] 다이나믹 프로그래밍 dp

 

문제

 

 

 1. Top Down, 재귀

N에 도달 가능 여부만 판단한다.

#include <iostream>
#include <cstring>
#include <cmath>
#define MAX_N 5001
using namespace std;
int N, K;
int e[MAX_N], dp[MAX_N];

// top - down
// 도달 가능 여부만 확인하면 된다
// 갈 수 있으면 바로 끝 
// 2중 for 사용 가능

int canGo(int target) {
    int& ret = dp[target];
    if (ret != -1) return ret;

    ret = 0; //0으로 설정, 일단 못간다 세팅  
    // i -> target으로 이동 
    for (int i = 0; i < target; i++) {
        int power = (target - i) * (1 + abs(e[target] - e[i]));
        if (power <= K) {
            if (canGo(i)) {
                return ret = 1; // 1
            }
        }
    }
    return ret; // 0
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> K;
    for (int i = 0; i < N; i++) cin >> e[i];

    memset(dp, -1, sizeof(dp)); //-1 : 아직 안봤다.
    dp[0] = 1; // 갈 수 있다.
    cout << (canGo(N-1) ? "YES" : "NO");
    return 0;
}

 

 

 

2. Bottom Up , 2 중 for

#include <iostream>
#include <cstring>
#include <cmath>
#define MAX_N 5001
#define INF 0x7f7f7f7f
using namespace std;
int N, K;
int e[MAX_N];
int dp[MAX_N];

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N >> K;
    for (int i = 1; i <= N; i++) cin >> e[i];

    memset(dp, INF, sizeof(dp));
    dp[0] = dp[1] = 0;
    for (int i = 1; i <= N - 1; i++) {
        for (int j = i + 1; j <= N; j++) {
            int power = (j - i) * (1 + abs(e[j] - e[i]));
            if (power > K || dp[i] == INF) continue;
            dp[j] = min(power, dp[j]);
        }
    }
    cout << ((dp[N] == INF) ? "NO" : "YES");
    return 0;
}

 

 

목표 지점에 도달 가능 여부만 판단하면 되기 때문에 1번 코드가 더 효율적이다.