백준 2748번 파이썬 풀이: 피보나치 수 2

백준 2748번 피보나치 수 2

 

알고리즘 분류: 다이나믹 프로그래밍, 수학

 

링크: https://www.acmicpc.net/problem/2748

 

2748번: 피보나치 수 2

 

문제

피보나치 수는 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번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

 

 

문제 파악

 

이번 문제는 수학을 좋아하는 사람이라면 한번 쯤 들어봤을 피보나치 수열 문제이다.

 

피보나치 수는 n번째 수는 n-1번째 수와 n-2번째 수의 합으로 이루어진다는 것이다.

 

자세한 내용은 링크 참고하면 좋을 것 같다.

 

코드

 

정답 코드를 보기 전에 처음에 재귀를 이용해서 풀었는데 시간초과가 났다.

 

시간 초과가 난 이유를 분석해 보자면 입력 값에 n이 90보다 작거나 같은 자연수인데

 

n이 90이라면 2의 90승을 계산해야되기 때문에 시간초과가 난 것으로 보인다.

 

예제를 입력해보았을 때 답이 잘 나오는 것으로 보아

 

간단한 수라면 이런 재귀를 통해서도 풀 수 있을것으로 보인다.

 

이제 정답 코드를 보자면

 

쉽게 말하자면 fibonacci라는 리스트를 만들어 이 수열들을 다 리스트에 넣어주었다.

 

피보나치 수는 n-2번째와 n-1번째의 합이기 때문에

 

num를 리스트의 -1번째 인덱스 와 -2번째 인덱스의 합으로 표현하였다.

 

n이 주어졌을 때 n번째 피보나치 수를 구해야하기 때문에 for문의 range를

 

n+1까지 설정해주어서 n번째 수까지 리스트에 다 넣어줄수 있도록 하였다.

 

마지막으로 출력에 n번째 피보나치 수를 출력하기 위해서

 

fibonacci 리스트의 마지막 인덱스를 출력해주면 n번째 피보나치 수가 출력된다.