프로그래머스 - 멀리 뛰기 (JAVA)

문제링크

 

 

문제 풀이 과정

이 문제를 잘 보면 f(n) = f(n - 1) + f(n - 2) 피보나치 수열이라는 것을 알수 있다.

 

 

5 까지의 경우의 수이다.

 

 

칸이 3일때를 보면 칸 2일때와 1일때의 값을 더한 값이 된다.

 

칸이 4일때도 칸이 3일때와 2일때의 값을 더한 값이 칸이 4일때의 값이 된다.

따라서 이 문제가 피보나치 수열이라는 것을 알 수 있다.

 

 

피보나치수열은 재귀호출을 이용하여 풀이하는 것과 dp 배열을 사용하여 풀이 하는 방법이 있는데 이 문제는 재귀 호출을 이용하면 통과가 안된다.

또한 dp 을 선언 할때 배열의 칸을 n + 1 만큼 잡았었는데 이러면 케이스 1이 통과가 안된다.

dp 배열의 길이를 매우 넉넉하게 잡거나 n + 2 만큼 잡으면 테스트 1이 통과가 된다.

 

 

 

전체 코드