[백준] 1003번 피보나치 함수 - 파이썬(Python)

문제 (링크)

https://www.acmicpc.net/problem/1003

1003번: 피보나치 함수

 

나의 풀이

n = int(input())
dp = [[0, 0] for _ in range(41)]
dp[0][0] = 1
dp[0][1] = 0
dp[1][0] = 0
dp[1][1] = 1

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

n_list = []
for _ in range(n):
    n_list.append(int(input()))
    
for n in n_list:
    print(dp[n][0], end=' ')
    print(dp[n][1])

풀이법 및 코드 설명

피보나치 수열의 리턴값을 fibo(n) = fibo(n-2) + fibo(n-1)이라고 정해두고 보면 굉장히 쉽게 풀릴 수 있는 문제였다.

 

먼저, n = 0일 때와 1일 때는 각각 fibo(0)과 fibo(1)은 [1, 0], [0, 1]번식 호출된다.

 

n = 2 일 때 호출되는 fibo(2)는 fibo(1) + fibo(0)이므로, fibo(2)가 fibo(1)과 fibo(0)을 호출하는 횟수는 n = 0일 때와 n = 1일 때 fibo(0)과 fibo(1)을 호출한 횟수를 더한 값과 같다.

 

n = 3 일 때, fibo(3) = fibo(2) + fibo(1)이므로, fibo(3)이 fibo(1)과 fibo(0)을 호출하는 횟수는 n = 2일 때와 n = 1일 때 fibo(0)과 fibo(1)을 호출한 횟수를 더하는 값과 같다.

 

이를 점화식으로 세우면, dp[n][0], dp[n][1] = dp[n-2][0] + dp[n-1][0], dp[n-2][1] + dp[n-1][1] 이라고 할 수 있다.



최대로 주어질 수 있는 N은 40이므로, 길이가 41만큼의 dp리스트를 만든 후, n이 0일 때와 1일 때만 직접 값을 채워넣어주고, 나머지 값들은 for문을 돌면서 점화식에 맞는 값을 삽입해주었다.

 

이 후, 입력 받은 값들을 하나 씩 돌면서 알맞은 dp리스트의 값을 출력해주었다.