🧮 [프로그래머스] 멀리 뛰기 (Java) - DP 문제

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12914

프로그래머스

 

문제 이해 & 풀이

문제를 이해하는 것은 아마 굉장히 편할 것이다 라고 생각한다.

 

하지만 풀이가 매우 중요한데 여기서 가장 눈여겨 보아야 할 것은 피보나치 수열을 사용할 수 있다는 것이다.

 

처음에 문제를 만나면 각각의 칸수를 계산하고 계산한 칸수를 저장하고 이런식으로 생각하기 마련이다. 

하지만 우리에게 중요한 것은 경우의 수가 무엇이냐가 아닌 경우의 수의 갯수이다

 

이를 알고 천천히 문제를 다시 보면 

1칸일 경우 => (1칸) - 1개
2칸일 경우 => (1칸, 1칸), (2칸) - 2개
3칸일 경우 => (1칸, 1칸, 1칸), (1칸, 2칸), (2칸, 1칸) - 3개
4칸일 경우 => (1칸, 1칸, 1칸, 1칸), (1칸, 2칸, 1칸), (1칸, 1칸, 2칸), (2칸, 1칸, 1칸), (2칸, 2칸) - 5개

1개, 2개, 3개, 5개 이런식으로 증가하는 것을 볼수 있다. 그렇다면 자연스럽게 5칸일 경우 8개가 될 것이다 라고 예측해볼 수 있다.

 

그럼 우린 피보나치 식(fibo(n-1) + fibo(n - 2))을 사용할 수 있겠다. 라고 생각이 들 수 있다. 하지만 중요한 것은 조건이다.

피보나치 수열은 O(2^N)의 시간 복잡도를 가지고 있다. 그럼 2000이면 2^2000인데 이는 너무 오래 걸린다. 그래서 우리는 DP를 사용할 것이다.

 

https://latewalk.tistory.com/171

동적 계획법 (DP, Dynamic Programming)

 

DP는 이미 계산했던 연산에 대해서 바로 불러낼수 있는 아주 큰 장점으로 인해 시간 복잡도가 굉장히 줄어드는 효과적인 연산방법을 사용할 수 있다.

 

소스 코드

주의할점은 배열의 크기에 + 1을 해주어야 한다는 것이다. 왜냐하면 우리는 index0에 데이터를 0을 넣어야한다. 그래야 몇번째 숫자에 원하는 연산 결과가 들어가기 때문이다. 또한 1일 경우의 답도 바로 줄 수 있게 만들어주어야 한다.