[DP/동적계획법] 백준 1003 피보나치 함수 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

1003번: 피보나치 함수

 

 

 

2. 문제 풀이

fibo[n] = fibo[n-1] + fibo[n-2]

 피보나치 수열에서 0과 1이 리턴되는 횟수를 구하는 문제입니다. 피보나치 수열은 이전 결과와 그 이전 결과의 합으로 구성됩니다. 따라서 몇 번째 피보나치 수이든, 2이상이면 반드시 0과 1을 1번 이상 호출해야 합니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 

n	0	1	2	3	4	5
fibo[0] 호출 횟수	1	0	1	1	2	3
fibo[1] 호출 횟수	0	1	1	2	3	5

 0과 1의 호출 횟수를 살펴보면, 피보나치 수열과 똑같은 규칙을 보입니다. 즉, 피보나치 수열을 구하는 것과 똑같은 문제입니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

fibo = [[-1] * 2] * 41 # [-1, -1]로 초기화 (최대 N은 40)
fibo[0] = [1, 0] #0의 갯수 / 1의 갯수
fibo[1] = [0, 1]

for i in range(2, 41):
    fibo[i] = [fibo[i-1][0] + fibo[i-2][0], fibo[i-1][1] + fibo[i-2][1]]

T = int(input())
for i in range(T):
    n = int(input())
    print(fibo[n][0], fibo[n][1])

 최대 N은 40까지입니다. 40까지 계산해두고 불러와서 사용합니다.

 테스트케이스가 1회 이상이므로, 매번 계산해서 푸는 것보다는 메모이제이션해서 불러오는 게 효율적입니다.