[백준/Baekjoon] 2253 점프 C++ :: Dynamic Programming

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

2253번: 점프

---

1. Logic

1번째 돌에서 시작하여 n번째 돌까지 가야하지만 중간에 밟지 못하는 돌이 존재한다. 이런 돌을 걸러주기 위해 bool배열을 통해 체크해준다. 재귀를 통해 0까지 들어가며 부문문제를 해결해준다. 부분문제는

1. 이전에 이동했던 칸수와 동일하게 이동하는 경우

2. 이전에 이동했던 칸수-1칸 이동하는 경우

3. 이전에 이동했던 칸수+1 이동하는 경우

이렇게 3가지 이다.

---

2. Code

#include <cstring>
#include <iostream>
#include <vector>

using namespace std;

int n, m;
const int INF = 0x3f3f3f3f;

int dp[10001][501];
bool che[10001];

int solve(int idx, int prev) {
    if (idx == n) return 0;
    if (idx > n || che[n]) return INF;
    int &ret = dp[idx][prev];
    if (ret != -1) return ret;

    ret = INF;

    if (!che[idx + prev]) {
        ret = min(ret, solve(idx + prev, prev) + 1);
    }
    if (!che[idx + prev - 1] && prev - 1 >= 0) {
        ret = min(ret, solve(idx + prev - 1, prev - 1) + 1);
    }
    if (!che[idx + prev + 1]) {
        ret = min(ret, solve(idx + prev + 1, prev + 1) + 1);
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    memset(dp, -1, sizeof(dp));

    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a;
        cin >> a;
        che[a] = true;
    }

    int ans = solve(1, 0);

    if (ans == INF)
        cout << -1;
    else
        cout << ans;

    return 0;
}

---

3. Feedback

만약 도달하지 못했을때의 기저조건을 처음에는 -1을 반환하는 것으로 해서 엄청 고전했다. 함수 안에서 min값으로 확인하기 때문에 만약 첫번째 ret값에서 -1을 가져왔다면 두번째에서는 -1보다 더 작은 수는 답이 절대로 될 수 없음으로 기저조건에서 INF를 반환해야 한다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐