알고리즘 역량테스트 문제/백준
[백준][c++] 11060번 점프 점프
coooding
2020. 8. 12. 14:20
문제
11060번 점프 점프
문제 링크
https://www.acmicpc.net/problem/11060
11060번: 점프 점프
재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 정수가 하나 쓰여 있다. i번째 칸에 쓰여 있는 수를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 �
www.acmicpc.net
풀이 과정
다이나믹 프로그래밍을 활용하여 출발지에서 부터 점프하여 갈 수 있는 값들을 비교하고 갱신하면서 값을 구합니다.
코드
#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];
}