[BOJ 11060] 점프 점프 C++

난이도: Silver 2
번호: 11060
사용 함수, 자료 구조: Memoization, Tabulation
생성일: February 28, 2023 3:28 PM
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색, 다이나믹 프로그래밍
언어: C++

11060번: 점프 점프

C++

BFS + memoization

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int N;
int arr[1002], memo[1002];

int BFS()
{
    queue<int> Q;
    memo[0] = 0;
    Q.push(0);

    while (!Q.empty())
    {
        int idx = Q.front();
        Q.pop();

        for (int k = 1; k <= arr[idx] && idx + k < N; k++)
        {
            int nextIdx = idx + k;
            if (memo[nextIdx] > memo[idx] + 1)
            {
                memo[nextIdx] = memo[idx] + 1;
                Q.push(nextIdx);
            }
        }
    }

    return memo[N - 1] == 2147483647 ? -1 : memo[N - 1];
}

int main()
{
    cin >> N;
    fill(memo, memo + 1002, 2147483647);
    for (int i = 0; i < N; i++)
        cin >> arr[i];
    int result = BFS();
    cout << result << endl;

    return 0;
}

C++

DP + Tabluation

#include <iostream>
#include <algorithm>
using namespace std;

int N, arr[1001], dp[1001];

void _dp()
{
    dp[0] = 0;
    for (int i = 0; i < N; i++)
        for (int k = 1; k <= arr[i] && (i + k) < N; k++)
            dp[i + k] = min(dp[i] + 1, dp[i + k]);
}

int main(void)
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        cin >> arr[i];
        dp[i] = 100000;
    }
    _dp();
    cout << (dp[N - 1] == 100000 ? -1 : dp[N - 1]);
}

참고

Memoization과 Tabulation: 다이나믹 프로그래밍(DP)의 두 가지 접근법