백준 BOJ <1003번> 피보나치 함수 || 파이썬

썸네일

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제에서 주어진 fibonacci 함수를 파이썬에서 작성하면 다음과 같은 재귀함수를 만들 수 있다.

 

피보나치 함수 파이썬

하지만 이를 그대로 이용해 문제를 풀려고 하면 런타임에러나 시간초과 메모리 초과등과 같은 문제를 띄울 것이다.

이유는 fibonacci 함수가 한 번 들어가면, 2번의 함수를 재귀 호출하기 때문이다.

실제로 시간 초과 에러를 띄움

 

따라서 이는 다른 방식으로 해결할 필요가 있다.

그 중 하나의 방법이 배열을 이용한 것이다.

그 이전에, 0과 1을 호출하는 횟수또한 피보나치 수열에 따른다는 것을 이해하고 가야한다.

간략하게 표시한 것이지만, 직접 해보면 이는 귀납적으로 성립한다.

따라서 최종 코드는 다음과 같다.

이때 c0은 0의 호출 횟수를, c1은 1의 호출 횟수를 담은 배열이다.

최종 코드

글쓴이 또한 피보나치 수열에서 0과 1을 호출하는 횟수가 피보나치 수열을 따른다는 것을 뒤늦게 알아차리고 배열을 통해 풀 수 있었다. 대부분의 블로그에서도 배열을 이용한 풀이가 대부분이다.

추가로, 놀랍게도 본인과 코드가 매우매우 비슷한 사람이 있었다는 것에 다시 한 번 놀랐다.

사람이 생각하는 것은 거기서 거기인가 보다