Baekjoon 문제 풀기 (2747번 : 피보나치 수) Python

2747번 : 피보나치 수

1. 문제읽기

---

피보나치 수열 구현하기

대표적인 피보나치 수열 계산하기 문제이다.
동빈북에서 잠깐 본 것으로 풀긴 했는데, 다시 공부해야겠다.

처음에 그냥 재귀를 썼다가, 시간초과로 실패해서 사전을 이용하여 한번 구한 값을 저장하여 반복되는 계산을 줄여서 성공했다.
반복문으로 구현할 수도 있지만, 재귀를 써보았다.

2. 제출 코드

---

feb_dic = {1: 1, 0: 0}


def feb(n):
    if n in feb_dic.keys():  # dic에 값이 있으면 값을 리턴
        return feb_dic[n]
    feb_dic[n] = feb(n-1) + feb(n-2)  # dic에 값이 없으면 새로 저장하고,
    return feb_dic[n]				  # 그 값을 리턴한다.


print(feb(int(input())))

3. 공부할 것

---