[백준] 1002 피보나치 함수 파이썬 풀이 (동적계획법)

문제

• 피보나치 함수를 구할때 0과 1이 몇 번 호출되는지 구하여라

 

문제 풀이

• fn_2 에 fibonacci(n-2)의 0의 개수와 1의 개수를 저장한다.
• fn_1에 fibonacci(n-1)의 0의 개수와 1의 개수를 저장한다.
• fn에 fibonacci(n)의 0의 개수와 1의 개수를 저장한다.
• fn의 0의 개수는 fn_1의 0의 개수와 fn_2의 0의 개수를 더한 것이다.
• fn의 1의 개수는 fn_1의 1의 개수와 fn_2의 1의 개수를 더한 것이다.
• fn에 저장해주고 나서 fn_1에 있던 값을 fn_2로 옮기고 fn에 있던 값을 fn_1로 옮긴다.

 

코드

num = int(input())
for i in range(num):
    number = int(input())
    fn_2 = [0,0] #f(n-2) 저장 0 인덱스의 값은 0이 나온 횟수 1인덱스의 값은 1이 나온 횟수
    fn_1 = [0,0] #f(n-1) 저장
    fn = [0,0] #fn 저장
    if number == 0:
        print('1 0')
       
    elif number == 1:
        print('0 1')
       
    else:
            
        for j in range(number+1):
            if j == 0:
                fn_2 = [1,0]
            elif j == 1:
                fn_1 = [0,1]
            else:
                fn[0] = fn_2[0] + fn_1[0]
                fn[1] = fn_2[1] + fn_1[1]
                fn_2[0],fn_2[1] = fn_1[0],fn_1[1]
                fn_1[0],fn_1[1] = fn[0],fn[1]
        print(fn[0], fn[1])

---

다른 사람의 풀이

t = int(input())
for i in range(t):
    n = int(input())
    zero = 1
    one = 0
    tmp = 0
    for _ in range(n):
        tmp = one
        one = one + zero
        zero = tmp
    print(zero, one)