점프 2253

문제

접근 방법

이전 돌에서 다음 돌로의 값을 탐색으로 확인해 주고 만약 다음 돌이 작은 돌인 경우 무시하는 방식으로 해결하면 된다.
DFS, BFS 모두 사용해 주어도 된다.

코드

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int, int> pii;
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int N, M;
    cin >> N >> M;
    vector<vector<int>> dp(N + 1, vector<int>(150, 10001));
    vector<bool> small(N + 1);
    while (M--)
    {
        int i;
        cin >> i;
        small[i] = true;
    }
    if (small[2])
    {
        cout << -1;
        return 0;
    }
    queue<pii> q;
    dp[2][1] = 1;
    q.push({2, 1});
    while (!q.empty())
    {
        pii cur = q.front();
        q.pop();
        int curIdx = cur.first, curVal = cur.second;
        if (cur.first == N)
        {
            cout << dp[curIdx][curVal];
            return 0;
        }
        for (int i = -1; i <= 1; ++i)
        {
            int nextVal = curVal + i, nextIdx = curIdx + nextVal;
            if (nextIdx > N || small[nextIdx] || dp[nextIdx][nextVal] <= dp[curIdx][curVal] + 1 || curVal == 0)
                continue;
            dp[nextIdx][nextVal] = dp[curIdx][curVal] + 1;
            q.push({nextIdx, nextVal});
        }
    }
    cout << -1;
    return 0;
}

풀이

만약 1차원 DP로 해결하려 하면 먼저 도착한 값에 의해 오류를 겪게 된다. (빠르게 도착하였지만 이후 작은 돌, N의 범위를 넘어선 값 등으로 제외된 경우)
그렇기에 2차원 DP로 해결하면 되는데 속도와 위치로 DP를 구성하면 된다. 속도 크기만큼 할당할 때 실수로 N의 크기만큼 할당했다. 속도는 1부터 시작하여 증가하기에 N에 도달하기 전까지 1부터 최대 속도까지의 합으로 이루어진다.
그렇기에 이러한 식이 만들어진다.
N = 1부터 최대 속도까지의 합 = 최대 속도*(최대 속도+1)/2