11060: 점프점프

이 문제는 처음엔 내가 있는 위치에서 최대한 멀리 뛰는 것을 생각했는데 자세히 살펴보니 dp를 이용해서 푼다는 것을 알았다. 그런데 내가 아직 dp가 익숙하지않아서 dp[i]에 들어갈 값이 점프해서 i노드까지 올 수 있는 최소 점프 수라는 것은 알았는데 이를 dp로 이용했다고 하기엔 애매한 부분이 있는 것 같다. 다른 잘 쓴 코드를 보면서 조금 더 학습해야겠다고 느꼈다. 

#include<iostream>
using namespace std;

int main() {
	
	int N = 0;
	cin >> N;
	int* arr =new int[N];
	int*road = new int[N];// 점프해서 i노드까지 올수있는 최소 점프 수
	fill_n(road, N, 10000); //큰수로 배열 초기화

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	
	road[0] = 0; //가장 처음 노드의 이동 횟수는 0
	for (int i = 0; i < N; i++) {
		for (int j = 1; j <= arr[i]; j++) {
			int read=road[i]+1; // 이전에 저장된 값에서 한번 움직인 것으로 +1
			if (i+j>N-1) //가장 마지막 노드까지 돌면 continue
				continue;
			else {
				if (read < road[i + j]) //기존에 저장된 값보다 현재 값이 적으면
				{
					road[i + j] = read; // 현재값을 넣음
				}
				else
					continue;
			}
		}
	}
	if (road[N - 1] == 10000) //최종 노드의 값이 변하지 않았으면
		cout << "-1"; //-1출력
	else cout << road[N - 1]; 
	

	return 0;
}