[백준] 2747번: 피보나치 수

링크: www.acmicpc.net/problem/2747

2747번: 피보나치 수

피보나치 수

문제

피보나치 수는 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은 45보다 작거나 같은 자연수이다.

출력

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

---

문제 접근

이번 문제는 피보나치 수열에 관한 문제이다. 저번에 피보나치 수 문제를 풀었을때, 동적계획법, 행렬곱셈 등등 여러 방법이 있다고 했었는데, 이 문제는 아마(?) 동적계획법을 통해 해결해야하는 문제이다. 애초에 문제 시간제한이 1초여서 제귀로 접근하면 아마 시간초과가 날것이다.

 

동적계획법으로 문제를 풀려고 보니 점화식은 Fn = Fn-1 + Fn-2 (n>=2) 이므로 문제 절반은 해결한 것이다.

나는 [0,1]인 리스트를 선언하고 2부터 입력으로 들어온 n번까지의 피보나치 수를 동적 계획법을 통해 만들었다.

---

코드

"""
백준 알고리즘 2747번: 피보나치 수
https://www.acmicpc.net/problem/2747

재귀함수로 안하고 동적프로그래밍 비스무리 하게 풀어봄
"""
import sys

fibo = [0, 1]

def calc(n):
    for i in range(2, n+1):
        fibo.append(fibo[i-1] + fibo[i-2])
    return fibo[n]


def main():
    n = int(sys.stdin.readline())
    print(calc(n))

if __name__ == "__main__":
    main()

재귀함수를 통해서 문제를 풀면 n=5일때만 해도 f(2)와 f(3)이 많이 호출된다. 이를 방지하고자 f(2)와 f(3) 등등 이전에 계산했던 값을 저장해서 fibo에 저장하여 사용한 것이다.