[백준][python] 1003.피보나치 함수 - 동적계획법

문제

• 백준 1003 피보나치 함수 Silver III
• python
• 문제링크

1003번: 피보나치 함수

나의 코드

원래 피보나치 문제를 풀듯이 재귀적으로 풀었는데 역시나 시간 초과 에러가 났다. 

여러번 반복되는 코드의 실행에서 바뀌지 않는 값들이 존재하기 때문에 매번 같은 연산을 반복할 필요가 없다. 따라서 이 문제는 동적계획법과 메모이제이션을 사용해서 풀어야한다. 메모이제이션이란, 자꾸만 반복되지만 그 결과값은 변하지 않는 작은 문제들의 결과값을 저장하는 것을 의미한다. 이 두가지 개념은 새로운 포스트에서 더 자세하게 다뤄보겠다.

# N이 0, 1 일때의 0과 1의 출현 빈도수
cnt0 = [1, 0]
cnt1 = [0, 1]

# t번의 테스트 케이스에서 같은 결과물을 사용할 것이기 때문에 N의 최대 수까지 계산을 해놓는다.
for i in range(2, 41):
    cnt0.append(cnt0[i-1]+cnt0[i-2])
    cnt1.append(cnt1[i-1]+cnt1[i-2])

for _ in range(int(input())):
    n = int(input())
    print(cnt0[n], cnt1[n])