[11060번] 점프 점프

문제 출처 :

https://www.acmicpc.net/problem/11060

알고리즘 분석 :

문제 해결에 필요한 사항

1. Dynamic Programming

점화식을 세우는 방식은 다음과 같다.

현재 자리에서 뛰려하는 위치에 만약 DP값이 있다면 

기존에 있던 DP값과 뛰어 올 때 생기는 DP값 두 값중 최소값을 구하여 갱신하면 된다.

i는 현재 위치이고 t는 뛸 수 있는 모든 경우를 표현한다.

소스 코드 : 

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 33 34 35 36 37 38 39 40 41 42 43 44 45

#include <iostream> #include <cstdio> #include <memory.h> #include <limits.h>   #define MIN(a,b)(a < b ? a : b)   using namespace std;   int arr[1001]; int DP[1001];   int main() {     int n;     scanf("%d", &n);       fill(DP, DP + n, INT_MAX);       for (int i = 0; i < n; i++)         scanf("%d", &arr[i]);       DP[0] = 0;       for (int i = 0; i < n; i++)     {         // 뛸 수있는 값         int jump = arr[i];                  // 뛸 수있는 모든 경우         for (int t = jump; t > 0; t--)         {             // 그 자리에서 뛰려할 때 그 자리에 DP값이 채워져있어야 한다.             if(DP[i] != INT_MAX)                 DP[i + t] = MIN(DP[i] + 1, DP[i + t]);         }     }       DP[n-1] == INT_MAX ? printf("-1") : printf("%d", DP[n - 1]);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus