백준 11060번 점프 점프

문제 링크입니다: https://www.acmicpc.net/problem/11060

간단한 메모이제이션을 이용하면 쉽게 풀 수 있는 문제였습니다.

최대 arr[i]만큼 움직이는 것이므로 1부터 arr[i]만큼 움직여보는 것이 핵심이였습니다.

#include <iostream>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int INF = 987654321;

const int MAX = 1000;

 

int N;

int arr[MAX];

int cache[MAX];

 

int minJump(int start)

{

        if (start == N - 1) //목적지 도달할 경우

               return 0;

        if (start >= N) //목적지 도달 못할 경우

               return INF;

        int &result = cache[start];

        if (result != -1)

               return result;

        result = INF;

        for (int i = 1; i <= arr[start]; i++) //arr[start]이하 갈 수 있으므로

               result = min(result, 1 + minJump(start+i));

        return result;

}

 

int main(void)

{

        cin >> N;

        if (N<1 || N>MAX)

               exit(-1);

 

        for (int i = 0; i < N; i++)

               cin >> arr[i];

 

        memset(cache, -1, sizeof(cache));

        int result = minJump(0);

        if (result == INF)

               cout << -1 << endl;

        else

               cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~