[백준] 10870번 피보나치 수 5 / Dynamic Programming(동적계획법)

 

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

10870번: 피보나치 수 5

---

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

---

내가 푼 코드

 

사실 좋은 방식인지는 모르겠지만.. 개념을 공부한 토대로 풀려고 최대한 노력하였다!

 

동적계획법이니까 배열도 동적으로 생성을 해야된다고 생각하여 ArrayList를 사용하였다.

0,1,2는 0,1,1로 고정 값이므로 미리 add로 추가 시켜두었다.

 

그 후에 n이 0,1,2이면 그에 맞는 index로 값을 answer에 담아 출력시켜주었다.

 

만약 n이 0~2가 아니라면 list의 크기-1과 n을 비교하고 n에 해당하는 list의 값이 0이 아니라면 바로 list에서 가지고 오도록 하였다.

 

피보나치 수를 구해야 하는 상황이라면 n까지 for문을 돌면서 list에서 최근 2개의 값에 해당하는 값을 가져와서 list에 추가하도록 하였다. 이 부분은 클래스로 만들었다면 재귀함수로 처리할 거 같다!

---

피보나치 수 문제를 풀기 전에 Dynamic Programming(동적계획법) 개념에 대해서 먼저 공부를 하였다.

 

참고한 영상은 아래 2가지이다!

https://www.youtube.com/watch?v=FmXZG7D8nS4 

https://www.youtube.com/watch?v=eJC2oetXaNk