[BAEKJOON/Python3] 백준 2748 피보나치 수 2

www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

＊링크로 접속하여 문제를 확인할 수 있습니다.

 

Fn = Fn-1 + Fn-2 (n ≥ 2) 인 피보나치 수를 구하는 문제인데 동적계획법을 이용해 해결해 볼 것 입니다.

 

※동적계획법(Dynamic Programming)은 문제를 작은 문제로 쪼개서 해결하되, 작은 문제의 솔루션을 모두 테이블에 저장하고 필요할 때 읽어와 사용할 수 있도록 하는 방법입니다. 동일한 값이 여러번 등장할 때 재귀를 여러번 호출하지 않고 저장한 값을 불러와 시간을 단축할 수 있다는 장점이 있습니다.

 

코드

 

몇번째 피보나치 수를 구하는지 입력받고 Fib라는 테이블을 만들어 피보나치 수열을 저장할 것입니다. 첫번째, 두번째 피보나치 수는 처음에 저장하고, 그 후부터는 식을 이용하여 테이블에 저장합니다. n개의 피보나치 수를 구했으므로 리스트의 마지막 값을 출력하면 n번째 피보나치 수를 구할 수 있습니다.