[백준 알고리즘] 11060번 점프 점프

문제

재환이가 1×N 크기의 미로에 갇혀있다. 미로는 1×1 크기의 칸으로 이루어져 있고, 각 칸에는 숫자가 하나 써있다. i번째 칸에 써있는 숫자를 Ai라고 했을 때, 재환이는 Ai이하만큼 오른쪽으로 떨어진 칸으로 한 번에 점프할 수 있다. 예를 들어, 3번째 칸에 써있는 숫자가 3이면, 재환이는 4, 5, 6번 칸 중 하나로 점프할 수 있다.

재환이는 지금 미로의 가장 왼쪽 끝에 있고, 가장 오른쪽 끝으로 가려고 한다. 이 때, 최소 몇 번 점프를 해야 갈 수 있는지 구하는 프로그램을 작성하시오. 만약, 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 Ai (0 ≤ Ai ≤ 100)가 주어진다.

출력은 재환이가 최소 몇 번 점프를 해야 가장 오른쪽 끝 칸으로 갈 수 있는지이다. 만약 가장 오른쪽 끝으로 갈 수 없는 경우에는 -1을 출력한다.

풀이

f(i) = i번째칸에서 가장 오른쪽 끝으로 가는데 필요한 점프횟수 

i==n ->점프에서 마지막으로 간거니까 return 0

i < n -> f(i+1부터 a[i]만큼)+1 중에 최소 

이렇게하면 맨 오른쪽으로 갈 수 있는지를 알 수가 없는거같다

변수를 한개 더 만들어서

f(i, k) = i번째칸에서 k만큼 점프했을 때 가는데 필요한 점프횟수 단 k는 A[i]보다 작거나 같다

f(i, k) = min ( f(i+k, 1에서부터 A[i+1]까지) )

이렇게 하니까 너무 복잡해서 어디서 틀린지 모르겠다 ㅠㅠ 질문검색을 찾아보니

f(i)로도 되는거같다... 다시 위에 경우로 풀어봐야겠다

*허무하다 위에 방법이 맞았다 ㅠㅠ 심지어 훨씬 간단하다...

코드

int jump(int i)

{

int j, result = impossible, a;

if(i == n)

return 0;

if(i > n)

return impossible;

if(dp[i] != -1)

return dp[i];

for(j=1; j<= A[i] ; j++){

result = min(result, jump(i+j)+1);

}

dp[i] = result;

return result;

}