백준 파이썬 1003번: 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

문제 유형: 다이나믹 프로그래밍

 

# Solution 1

test_case = int(input())

for _ in range(test_case):
    n = int(input())
    k = n - 1
    a, b = 0, 1

    while k > 0:
        a, b = b, a + b
        k -= 1

    if n == 0:
        print(1, 0)
    else:
        print(a, b)

 

우선 fibonacci(N)을 호출했을 때 fibonacci(1)과 fibonacci(0)이 몇 번 호출되었는지 표로 정리해보면 아래와 같다.

N	0	1	2	3	4	5	6	7	8
fibonacci(N)	0	1	1	2	3	5	8	13	21
0이 호출된 횟수	1	0	1	1	2	3	5	8	13
1이 호출된 횟수	0	1	1	2	3	5	8	13	21

결국 호출 횟수 또한 피보나치 수열을 따르고 있다는 걸 알 수 있다. fibonacci(N)과 1이 호출된 횟수는 같고 0이 호출된 횟수는 fibonacci(N-1)과 동일하다.

 

이에 따라 구현해주고 fibonacci(0)일 경우만 예외 처리해준다.