1003 피보나치 함수

문제

피보나치함수는 f(0),f(1) = 1 이고, n > 2일때, f(n) = f(n-1) + f(n-2)로 표현할 수 있다.

이때, f(n)을 호출했을 때, f(0), f(1)이 호출된 숫자를 출력하는 문제이다.
Link: 피보나치 함수

코드

def sol(x):
    if(x == 0):
        print(1, 0)
        return
    if(x == 1):
        print(0, 1)
        return
    x1, y1, x2, y2 = 1, 0, 0, 1
    while(1 < x):
        x1, y1, x2, y2 = x2, y2, x1+x2, y1+y2
        x -= 1
    print(x2, y2)

n = int(input())
data = []
for i in range(n):
    data.append(int(input()))
for i in data:
    sol(i)

사용된 알고리즘

1. 다이나믹 프로그래밍

해설

이 문제는 피보나치 함수의 n번째 항을 구하는 문제와 같다
n번째항은 함수의 값을 더해갔다면, 이 문제는 f(0), f(1)이 호출된 수를 더해가면 쉽게 풀 수 있다.

왜냐하면 f(22)의 f(0) 호출 수는 f(21)의 f(0) 호출 수 + f(20)의 f(0) 호출 수와 똑같기 때문이다.

1. n이 0이나 1일 경우, 정해진 값을 리턴한다.
2. 1 < x이면 밑에서부터 f(0)과 f(1) 호출 수를 누적해나가면서 값을 구한다.