BOJ 11060번 점프 점프

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

github : https://github.com/junho0956/Algorithm/blob/master/11060/11060/%EC%86%8C%EC%8A%A4.cpp

 

맨 앞부분이 0일 경우 이동할수있는 경우의 수가 없으니 무조건 -1을 출력하도록 했는데,

만약 길이가 1이고 값이 0이면 이동하지 않아도 되니 0을 출력해도 되는 함정이 숨어있었습니다,,

 

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
#define val 987654321
 
int dp[1001];
int arr[1001];
int N;
int answer;
bool check = false;
 
int solve(int x) {
    
    if (x == N - 1) {
        check = true;
        return 0;
    }
    
    int& res = dp[x];
    if (res) return res;
 
    int ans = val;
    for (int i = arr[x]; i >= 1; i--) {
        if (x + i < N && arr[x + i] != 0) ans = min(ans, solve(x + i)+1);
    }
    return res = ans;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    if (arr[0] == 0) {
        if (N == 1) cout << "0";
        else cout << "-1";
    }
    else {
        answer = solve(0);
        if (check) cout << answer;
        else cout << "-1";
    }
 
    return 0;
}