점프점프

www.acmicpc.net/problem/11060

11060번: 점프 점프

#include <iostream>
#include <cstring>

using namespace std;


int main() {
	int n;
	int check[1001] = { 0, };
	check[1] = 1;
	cin >> n;
	int num;
	for (int i = 1; i <= n; i++) {
		cin >>num ;
		if (check[i] == 0) continue;
		for (int j = 1; (j <= num) && (i + j <= 1000); j++) {
			if (check[i + j] > check[i] + 1 || check[i + j] == 0) {
				check[i + j] = check[i] + 1;
			}
		}
	}
	
	if (check[n] == 0) { cout << -1 << endl; }
	else { cout << check[n] - 1 << endl; }
}

어떤알고리즘 어떤논리로?

- 다이나믹프로그래밍으로 풀었다. 첫번째 부터 시작해서 갈수있는 목적지까지 몇번 이동했는지 기록을 하는 메모이제이션(?) 기법을 사용했다. 그리고 만약에 기존에 기록한것보다 더 작은 값이 있으면 그 값으로 바꿔준다. 

어려웠던점

- 생각하는 것 만큼 구현하는게 조금 까다로웠다. 그래서 다른코드를 참고하기도 했다.