[백준 11060번] 점프 점프 |DP연습|

11060번: 점프 점프

입력

1. 미로 길이 N(1 ≤ N ≤ 1,000)

2. i타일에 적혀있는 숫자 = i타일의 점프숫자

Ai (0 ≤ Ai ≤ 100)

___________________________________________________

출력

1.재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지 출력한다. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

(주의사항) 

필자는 cout << '-1' << '\n'

이런식으로 썻다가 봉변당했다...

쓸거면 '-1'가 아니라 "-1"든지 -1을 써야한다.

'-1' != -1 임을 명심하자;;

___________________________________________________

생각방법

DP문제다.

점화식을 고민하자

20. 다이나믹 프로그래밍(Dynamic Programming)

___________________________________________________

과정

___________________________________________________

예제들

--------------------------------------

입력

15

4 5 2 5 5 4 0 1 3 4 1 2 0 2 3

출력

4

--------------------------------------

입력

6

0 0 1 0 1 1

출력

-1

--------------------------------------

입력

8

2 2 2 2 2 2 3 1

출력

4

--------------------------------------

입력

30

12 3 14 1 12 0 13 3 11 11 7 0 10 12 1 2 5 0 8 8 10 8 8 5 0 3 11 7 9 14

출력

3

--------------------------------------

입력

25

0 11 3 1 8 11 2 2 1 6 5 10 1 4 5 3 6 9 5 10 3 10 3 0 7

출력

-1

--------------------------------------

https://colorscripter.com/

#include <iostream>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <vector>
#include <string>
#define min(a, b) a > b ? b : a
 
using namespace std;
 
int dp[10001] = { 0, }; int A[10001] = { 0, }; bool is_dp_cal[10001] = { false, };
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    //______________________입력
    int N; cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> A[i]; 
        dp[i] = 999999;
    }
 
 
    //______________________dp 초기화
    dp[0] = 0;
    for (int i = 0; i < N; i++)
    {
        if (A[i] != 0) {
            for (int j = 1; j <= A[i]; j++) {
                if (i + j >= N)
                    dp[i + j] = dp[i] + 1;
                else
                    dp[i + j] = min(dp[i + j], dp[i] + 1);
            }
        }
    }
    //______________________
 
    if (dp[N - 1] > 1001)
    {
        cout << -1 << '\n';
    }
    else
        cout << dp[N - 1] << '\n';
 
}