[BOJ]11060번: 점프 점프 (c++)

www.acmicpc.net/problem/11060

11060번: 점프 점프

 

DP

#include <iostream>
#include <vector>

using namespace std;

int N;
const int MAX = 1000;

void get_min_jump_cnt(vector<int> &maze, vector<int> &DP, int strt)
{
    for (int i = maze[strt]; i > 0; --i)
    {
        int next = strt + i;
        if (next < N && DP[next] > DP[strt] + 1)
        {
            DP[next] = DP[strt] + 1;
            get_min_jump_cnt(maze, DP, next);
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    // 입력
    cin >> N;
    vector<int> maze(N);
    for (int i = 0; i < N; ++i)
    {
        cin >> maze[i];
    }

    // DP[i] : 0번째 칸에서 i번째 칸까지 이동시 최소로 jump한 횟수
    vector<int> DP(N, MAX);
    DP[0] = 0;
    get_min_jump_cnt(maze, DP, 0);

    // 출력
    cout << (DP[N - 1] == MAX ? -1 : DP[N - 1]);

    return 0;
}

 

 

재환이는 지금 1×N 크기의 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다.
이때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오.

i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 
N(1 ≤ N ≤ 1,000)
Ai(0 ≤ Ai ≤ 100)

 

같은 지점에 여러차례 도달할 수 있으며, 

가장 처음으로 도달한 점프횟수보다 나중에 더 적은 점프횟수로 도달할 수 있다.

따라서 그리디나 BFS로 풀면 안되고 DP로 풀어야 한다. 

최소 점프 횟수를 기록하고 갱신해야 하기 때문이다.

 

 

예를 들어, 3번째 칸에 쓰여 있는 수가 3이면,
재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

위의 예시에서 4, 5, 6번 칸의 점프횟수는 3번칸의 점프횟수 + 1이 된다.

이때 4, 5, 6번 칸의 기존 점프횟수가 3번칸의 점프횟수 + 1 보다 작다면 다시 방문할 필요가 없어진다.

if (next < N && DP[next] > DP[strt] + 1)
{
    // 최소기록 갱신
    DP[next] = DP[strt] + 1;
    // next인덱스로 재귀함수 호출
    get_min_jump_cnt(maze, DP, next);
}