[백준] 2253번 : 점프 (C++)

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을 출력한다.

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <limits.h>
 
using namespace std;
 
int n, m;
vector<int> vec;
 
// 점프할 수 있는 최대거리를 충분히 잡지 못해서 계속 틀렸었다.
// 왜 처음 풀 때는 점프거리를 100정도까지밖에 잡지 않았는지 모르겠다.
// 정보를 찾다보니 k(k+1)/1 <= 10000을 만족하는 k의 최대 값이 m의 범위라고 한다.
int dp[10010][250];
 
int recur(int cur, int acc)
{
    // 1번 돌 이상 간 상황에서, 가속도가 0 이하라면
    if (cur != 1 && acc < 1) return 9999999;
    
    // n번째 돌 이상으로 갔을 경우
    if (cur > n) return 9999999;
 
    // 크기가 작은 돌을 밟았을 경우
    for (int i = 0; i < m; i++)
    {
        if (cur == vec[i]) return 9999999;
    }
 
    // 목표 돌에 도달했을 경우
    if (cur == n)
    {
        return 0;
    }
 
    if (dp[cur][acc] != -1)
    {
        return dp[cur][acc];
    }
 
    int ret = INT_MAX;
 
    // 처음 점프일 경우에,
    if (cur == 1)
    {
        // 무조건 다음 돌로 점프해야 한다.
        ret = min(ret, recur(cur + 1, 1) + 1);
    }
    else
    {    // x-1칸, x칸, x+1칸 점프하는 경우중 최소값을 가진다.
        for (int i = -1; i < 2; i++)
        {
            ret = min(ret, recur(cur + acc + i, acc + i) + 1);
        }
    }
 
    dp[cur][acc] = ret;
 
    return dp[cur][acc];
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n >> m;
    fill(dp[0], dp[0] + 10001 * 250, -1);
    
    vec.resize(m, 0);
    for (int i = 0; i < m; i++)
    {
        cin >> vec[i];
    }
 
    int result = recur(1, 1);
    if (result >= 9999999)
    {
        cout << -1;
    }
    else
    {
        cout << result;
    }
 
    return 0;
}
 

---

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

2253번: 점프