[ BOJ ] 14495 : 피보나치 비스무리한 수열 ( SILVER 5 ) / 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번째 피보나치 비스무리한 수를 출력한다.

풀이 과정

다이나믹 프로그래밍을 이용해 피보나치 수를 구하는 것처럼 dp[n] = dp[n - 3] + dp[n - 1] 을 이용했다.

import sys
input = sys.stdin.readline

n = int(input())
dp = [0 for _ in range(n + 1)]
dp[1] = 1
if n >= 2: dp[2] = 1
if n >= 3: dp[3] = 1

for i in range(4, n + 1): dp[i] = dp[i - 3] + dp[i - 1]

print(dp[n])