[백준 C++] 2253번 점프

2253번: 점프

문제 요약

문제

N(2 ≤ N ≤ 10,000)개의 돌들이 같은 간격으로 놓여 있다. 편의상 순서대로 1, 2, …, N번 돌이라고 부르자. 당신은 현재 1번 돌 위에 있는데, 이 돌들 사이에서 점프를 하면서 N번째 돌로 이동을 하려 한다. 이때 다음 조건들이 만족되어야 한다.

1. 이동은 앞으로만 할 수 있다. 즉, 돌 번호가 증가하는 순서대로만 할 수 있다.
2. 제일 처음에 점프를 할 때에는 한 칸밖에 점프하지 못한다. 즉, 1번 돌에서 2번 돌이 있는 곳으로 점프할 수 있다. 그 다음부터는 가속/감속 점프를 할 수 있는데, 이전에 x칸 점프를 했다면, 다음번에는 속도를 줄여 x-1칸 점프하거나, x칸 점프하거나, 속도를 붙여 x+1칸 점프를 할 수 있다. 물론 점프를 할 때에는 한 칸 이상씩 해야 한다.
3. 각 돌들은 각기 그 크기가 다르고, 그 중 몇 개의 돌은 크기가 너무 작기 때문에 당신은 그러한 돌에는 올라갈 수 없다. 위와 같은 조건들을 만족하면서 1번 돌에서 N번 돌까지 점프를 해 갈 때, 필요한 최소의 점프 횟수를 구하는 프로그램을 작성하시오.

사용 알고리즘

다이나믹 프로그래밍

입출력

• 입력: 첫째 줄에 두 정수 N, M(0 ≤ M ≤ N-2)이 주어진다. M은 크기가 맞지 않는, 즉 크기가 작은 돌의 개수이다. 다음 M개의 줄에는 크기가 작은 돌들의 번호가 주어진다. 1번 돌과 N번 돌은 충분히 크기가 크다고 가정한다.
• 출력: 첫째 줄에 필요한 최소의 점프 횟수를 출력한다. 만약 N번 돌까지 점프해갈 수 없는 경우에는 -1을 출력한다. ``` 예제1

입력 19 3 11 6 16 출력 6

## 풀이
2차원 dp를 쓰는 문제이다. 한축을 돌로 하고 한축은 점프의 이동 거리를 해서 풀면 된다. 

## 어려웠던 점
dp를 잡을때 무지성으로 최대 크기로 잡으면 메모리 초과가 난다. 제곱근 만큼 점프 안하기 때문에 그만큼만 잡아도 된다.

## 배운 점 / 느낀 점
메모리도 무지성으로 사용하지 말자

## 전체 코드
```cpp
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<bool> banned(N + 1, false);
    for (int i = 0; i < M; ++i) {
        int x; cin >> x;
        banned[x] = true;
    }

    int L = static_cast<int>(sqrt(2 * N)) + 2;

    vector<vector<int>> dist(N + 1, vector<int>(L + 1, INF));
    queue<pair<int,int>> q;

    /* 시작: 돌 1 에서 jump 길이 0 (아직 점프 안 함) */
    dist[1][0] = 0;
    q.push({1, 0});

    while (!q.empty()) {
        auto [pos, j] = q.front(); q.pop();
        int d = dist[pos][j];

        for (int nj = max(1, j - 1); nj <= j + 1; ++nj) {
            if (nj > L) continue;
            int np = pos + nj;
            if (np > N || banned[np]) continue;
            if (dist[np][nj] > d + 1) {
                dist[np][nj] = d + 1;
                q.push({np, nj});
            }
        }
    }

    int ans = *min_element(dist[N].begin(), dist[N].end());
    cout << (ans == INF ? -1 : ans);
    return 0;
}