백준 2253번 점프

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

오랜만에 다이나믹 프로그래밍 문제였습니다.

알고리즘은 아래와 같습니다.

1. N의 범위는 최대 10000이고 M의 범위는 대략 log(N) + α 이기 때문에 캐시 배열을 [10000+1][250] 정도로 잡아줬습니다.

-> (k)(k+1)/2 <= 10000를 만족하는 k의 최대값이 M의 범위입니다.

2. jump 함수를 호출하고 감속, 속도 유지, 증속을 하는데 범위를 초과하지 않고 갈 수 있는 돌이고 속도의 크기가 1 이상일 때만 재귀함수를 호출합니다.

3. boolean 값 success가 true일 때만 N번째 돌에 도달했다는 뜻이므로 success가 true이면 result를 출력해주고 false라면 -1을 출력해줍니다.

*초기 속도를 0이 아닌 1로 해서 계속 WA가 떴었습니다...

#include <iostream>

#include <vector>

#include <algorithm>

#include <cstring>

using namespace std;

 

const int MAX = 10000 + 1;

const int INF = 987654321;

 

int N, M;

bool success;

bool rock[MAX];

int cache[MAX][250];

 

int jump(int idx, int len)

{

        //조건 만족

        if (idx == N)

        {

                 success = true;

                 return 0;

        }

 

        int &result = cache[idx][len];

        if (result != -1)

                 return result;

 

        result = INF;

        for (int i = -1; i <= 1; i++)

        {

                 //다음 속도가 1 이상이고

                 if ((len + i) >= 1)

                 {

                         int next = idx + (len + i);

                         //범위 내에 있는 돌이고 갈 수 있는 돌일 때만 재귀함수 호출

                         if (next <= N && !rock[next])

                                 result = min(result, 1 + jump(next, (len + i)));

                 }

        }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        cin >> N >> M;

 

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

        {

                 int num;

                 cin >> num;

 

                 rock[num] = true;

        }

 

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

        int result = jump(1, 0);

        if (success)

                 cout << result << "\n";

        else

                 cout << -1 << "\n";

        return 0;

}

개발환경:Visual Studio 2017

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