[Python] 백준/BOJ 1003번: 피보나치 함수 (Silver 3)

💻 Problem

문제 보러 가기

 

N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

 

💡 Approach

이 문제의 시간 제한은 0.25초이다.

1초가 약 1억이니 0.25초면 약 25,000,000이다.

피보나치의 기본 재귀 코드는 시간복잡도가 2^n이기에 재귀로 풀면 안 된다.

 

피보나치 수열은 n이 2 이상일 때, f(n) = f(n-1) + f(n-2) 이다.

재귀로 풀면 f(n)을 구할 때, f(n-1)을 구하기 위해 f(n-2)를 계산했음에도 f(n-2)를 다시 구해서 f(n-1)과 더해야 한다.

출처: https://hongjw1938.tistory.com/47

 

사진으로 보면 이해하기 더 쉽다.

위 사진에서 f(5)를 구하려고 할 때, 중복 계산이 여러 번 발생하는 것을 확인할 수 있다.

 

DP로 풀면 메모이제이션을 통해 중복 계산을 막으므로 시간이 훨씬 빠르다.

0부터 쭉 대입해 보면 점화식을 찾을 수 있다.

# 주어지는 것
f(0) -> [1, 0]
f(1) -> [0, 1]

# f(n) = f(n-1) + f(n-2) 식을 통해 구한 것
f(2) = f(1) + f(0) -> [1, 1]
f(3) = f(2) + f(1) -> [1, 2]
f(4) = f(3) + f(2) -> [2, 3]
f(5) = f(4) + f(3) -> [3, 5]
f(6) = f(5) + f(4) -> [5, 8]
...

 

배열 안에 있는 두 숫자는 순서대로 0이 출력되는 횟수, 1이 출력되는 횟수이다.

이렇게 대입해 보면 점화식을 찾을 수 있다.

 

점화식: dp[i] = [dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1]]

 

점화식만 찾으면 코드 작성은 간단하다.

 

✏️ Solution

import sys
input = sys.stdin.readline

dp = [[]] * 41
dp[0] = [1, 0]
dp[1] = [0, 1]

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

t = int(input())
for _ in range(t):
    n = int(input())
    print(*dp[n])

미리 계산해 둔 dp 테이블에서 조회하는 것을 테스트 케이스만큼 수행하므로 시간 복잡도는 O(t + n)이다.

여기서 n은 문제에서 주어진 대로 최대 40이다.