[BAEKJOON] 11060 점프 점프

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <vector> #include <algorithm> #define MAX 2e9 using namespace std;   int main() {     int n;     vector<int>map(1001), DP(1001, MAX);       scanf("%d", &n);       for (int x = 0; x < n; x++)         scanf("%d", &map[x]);       DP[n - 1] = 0;       for (int x = n - 2; x >= 0; x--)     {         for (int jump = 1; jump <= map[x]; jump++)         {             if (x + jump < n)                 DP[x] = min(DP[x], DP[x + jump] + 1);         }     }       printf("%d\n", DP[0] == MAX ? -1 : DP[0]);       return 0; }

맨 뒤의 경우의 수를 0으로 둔다

그리고 그 이전으로 가면서

map의 숫자가 갈 수 있는 곳에 저장된 DP에 1을 더하여

가장 작은 것을 구한다