[백준][c++] 11060번 점프 점프

문제

11060번 점프 점프

 

문제 링크

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

11060번: 점프 점프

풀이 과정

 

다이나믹 프로그래밍을 활용하여 출발지에서 부터 점프하여 갈 수 있는 값들을 비교하고 갱신하면서 값을 구합니다.

 

 

코드

#include <iostream>
using namespace std;
int arr[1000];
int dp[1000];
int n;
int main(){
	cin >> n;
	for (int i = 0; i < n; ++i)
	{
		cin>>arr[i];
		dp[i]=987654321;
	}
	dp[0]=0;
	for (int i = 0; i < n; ++i)
	{	
		for (int j = 1; j <=arr[i]; ++j)
		{
			if(j+i>=n)
				break;
			if(dp[i+j]>dp[i]+1){
				dp[i+j]=dp[i]+1;
			}
		}
	}
	if(dp[n-1]==987654321)
		dp[n-1]=-1;
	
	cout<<dp[n-1];
}