11060: 점프점프 (DP) - 실패

풀이

뒤부터 체크해서 넘어가면 1로 설정하고 그 앞의 값은 해당하는 값만큼 앞의 수를 체크하는 방식으로 구현하였다. 하지만 모든 입출력에서 맞는데 왜 틀리는지는 잘모르겠음,,

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		int[] arr = new int[N];
		int[] cnt = new int[N];
		boolean flag = false;
		StringTokenizer st = new StringTokenizer(br.readLine());
		for (int i = 0; i < N; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
			cnt[i] = -1;
		}
		for (int i = N - 1; i >= 0; i--) {
			if (N == 1 && arr[0] == 0) {
				cnt[0] = 0;
				continue;
			}
			if (arr[i] == 0)
				continue;
			int tmp = i + arr[i];
			if (tmp >= N) {
				cnt[i] = 1;
				continue;
			}
			int min = N;
			for (int j = i + 1; j <= tmp; j++) {
				if (cnt[j] == -1) {
					flag = false;
					continue;
				}
				flag = true;
				if (min > cnt[j]) {
					min = cnt[j];
				}
			}
			if (flag)
				cnt[i] = min + 1;
			else
				cnt[i] = -1;
		}
		System.out.println(cnt[0]);
	}
}

 

10
1 2 0 1 3 2 1 5 4 2
output : 5

10
1 1 0 1 1 1 1 1 1 1
output : -1

5
0 0 0 1 0
output : -1

5
1 0 0 1 0
output : -1

3
0 1 0
output : -1

2
1 0
output : 1

1
0
output : 0

999
76 79 83 6 31 82 4 56 76 20 1 3 95 59 21 35 97 49 25 39 82 82 38 34 74 64 52 69 80 8 41 38 37 97 37 63 84 39 88 69 63 64 77 99 87 4 79 75 9 17 91 78 31 86 85 87 77 21 21 35 95 28 97 90 37 23 89 62 81 69 28 74 58 2 1 89 70 44 52 8 94 10 91 2 6 33 13 23 16 5 43 37 72 15 88 89 3 44 87 36 21 55 74 7 7 46 38 6 17 34 31 78 69 72 48 27 87 66 11 89 69 66 60 50 48 43 85 99 67 49 49 66 51 61 18 23 88 78 95 6 4 26 15 34 7 46 96 68 12 73 78 85 59 4 16 36 48 43 36 3 59 61 82 35 83 46 21 9 7 6 12 20 25 61 81 68 66 13 70 85 60 98 17 50 2 27 39 34 84 39 33 99 96 83 37 90 1 7 42 53 22 51 75 42 68 16 38 69 12 84 78 60 60 32 58 97 29 65 2 83 74 13 53 0 68 7 91 67 45 2 32 24 38 46 80 18 8 79 1 63 77 92 83 10 86 9 57 61 78 84 22 87 50 86 87 85 54 94 99 69 51 99 74 51 63 25 33 88 67 31 26 92 96 71 17 48 64 37 21 25 43 9 59 71 100 92 26 83 28 94 28 1 49 35 26 13 81 37 99 29 76 75 33 15 33 47 68 87 40 48 7 7 26 38 63 85 91 56 3 97 52 60 46 4 81 36 63 20 55 88 51 79 11 68 33 50 4 28 28 90 82 72 2 21 0 98 52 49 11 45 22 21 95 46 45 58 78 39 23 36 82 12 2 4 36 99 19 67 74 52 42 28 70 67 71 1 53 6 76 6 31 51 91 9 29 32 65 91 20 21 27 5 9 51 23 56 82 6 17 72 36 26 52 84 27 39 7 37 71 60 77 40 5 93 26 97 19 69 99 81 40 46 66 84 65 90 26 40 58 19 41 45 28 47 93 13 77 90 7 43 75 55 10 33 29 41 93 93 98 61 77 55 40 18 4 33 44 4 51 69 95 83 90 31 81 30 63 73 14 24 68 47 52 61 4 0 69 70 38 100 86 77 88 67 66 94 31 73 92 37 5 27 47 5 32 41 94 48 51 38 20 90 4 7 21 42 86 73 58 92 21 14 18 28 50 87 11 74 44 54 33 4 63 71 95 69 27 34 50 71 5 76 88 24 71 66 21 69 45 100 52 94 26 58 66 63 48 16 7 97 88 64 96 63 79 23 90 4 4 59 54 72 72 8 45 100 51 44 88 86 98 21 70 5 22 38 55 16 100 58 65 80 95 14 33 22 43 42 52 51 100 63 80 64 75 79 40 41 91 28 57 14 70 78 57 0 41 23 3 87 61 31 87 49 32 63 93 76 80 13 66 82 87 35 34 77 92 96 35 19 85 22 77 90 86 27 73 97 99 83 24 62 93 81 18 59 84 99 61 68 90 38 32 32 67 50 56 24 62 19 71 44 68 74 43 6 9 97 96 99 18 11 46 94 78 68 86 61 52 96 27 49 96 68 98 44 83 13 27 100 24 41 85 74 1 77 30 36 90 12 66 89 18 1 33 12 49 46 36 61 74 75 85 96 98 36 41 29 28 64 93 7 37 90 43 35 42 67 77 87 88 39 18 1 96 42 64 14 61 74 95 26 23 88 26 22 87 3 6 69 8 26 47 61 79 82 19 62 79 72 49 23 38 98 29 60 37 31 72 41 87 80 51 10 23 2 4 38 52 85 30 94 12 72 42 57 62 50 77 74 54 32 54 2 70 67 88 100 70 23 61 100 27 63 14 30 87 100 2 34 16 61 79 39 17 83 31 82 90 8 34 69 51 44 41 90 66 97 26 66 31 65 91 41 86 75 28 85 69 46 24 38 13 74 53 42 55 83 55 98 17 30 74 50 17 52 1 6 14 74 72 50 58 44 68 30 92 83 10 50 83 97 85 47 93 34 44 60 36 78 92 65 9 12 9 9 35 74 55 49 98 74 12 22 52 75 11 9 3 74 33 87 70 25 73 23 48 50 11 70 33 25 74 22 17 89 77 53 73 77 5 92 11 68 76 25 29 62 4 80 56 32 77 88 32 39 88 21 15 60 33 48 71 19 4 70 74 91 86 88 10 31 25 51 88 48 64 83 6 79 80 93 52 99 5 29 47 11 55 64 75 71 7 82 74 5 7 75 37 52 51 9 29 53 79 29 46 50 56 14 100 88 35 15 3 9 20 90 26 54 68 80 41 81 32 38 2 50 18 65 58 57 56
output : 12
1000
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output : -1

- 반례 모두 맞는걸 확인했는데 제출시 실패,,, 이유 차후에 공부 더 하고 찾아볼 예정