[백준] #14495 피보나치 비스무리한 수열(python)

📌문제

피보나치 비스무리한 수열은 f(n) = f(n-1) + f(n-3)인 수열이다. f(1) = f(2) = f(3) = 1이며 피보나치 비스무리한 수열을 나열하면 다음과 같다.

1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...

자연수 n을 입력받아 n번째 피보나치 비스무리한 수열을 구해보자!

입력

자연수 n(1 ≤ n ≤ 116)이 주어진다.

출력

n번째 피보나치 비스무리한 수를 출력한다.

예제 입력

10

예제 출력

19

백준 14495번 문제

💡Idea

DP를 이용하여 문제를 풀 수 있습니다.

점화식은 아래👇와 같습니다.

$f(n) = f(n-1) + f(n-3)$
$f(1) = f(2) = f(3) = 1$

💻코드1

• ⏰ 시간 : 72 ms / 메모리 : 30840 KB

반복문을 이용한 bottom up 방식의 DP 코드입니다.

import sys
n = int(sys.stdin.readline())

dp = [0, 1, 1, 1] + [0] * (n - 3) # 기본값 설정, f(n)의 값 저장
for i in range(4, n + 1): # f(4)부터 f(n)까지 계산
    dp[i] = dp[i - 1] + dp[i - 3]
print(dp[n])

💻코드2

• ⏰ 시간 : 72 ms / 메모리 : 30840 KB

재귀 함수를 이용한 top down 방식의 DP 코드입니다.

import sys
n = int(sys.stdin.readline())

dp = [0, 1, 1, 1] + [0] * (n - 3)
def top_down(n):
    if not dp[n]: dp[n] = top_down(n - 1) + top_down(n - 3) # 아직 계산 안 된 값인 경우
    return dp[n]
print(top_down(n))