백준 1003 - 피보나치 함수 (Python3)

코드

T = int(input())

for i in range(T):
    n = int(input())
    
    if n == 0:
        print(1, 0)
        continue
    
    if n == 1:
        print(0, 1)
        continue
    
    d = [0] * (n+1)

    d[1] = 1
    d[2] = 1
    
    for j in range(3, n+1):
        d[j] = d[j-2] + d[j-1]
        
    print(d[n-1], d[n])

문제 해설

DP를 이용하여 피보나치 함수를 구현하였다. 이 때, 문제에서 0과 1의 호출 횟수를 구하라고 하였는데, n이라는 숫자에 피보나치 함수를 적용하는 경우

1. n의 피보나치 함수 결과값 = 1의 호출 횟수
2. (n-1)의 피보나치 함수 결과값 = 0의 호출 횟수

라는 것을 알게 되어 이 성질을 이용하여 풀면 간단하게 해결되는 문제이다.