[백준/Python] 14495번: 피보나치 비스무리한 수열

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

14495번: 피보나치 비스무리한 수열

유형

다이나믹 프로그래밍

문제

피보나치 비스무리한 수열은 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번째 피보나치 비스무리한 수를 출력한다.

소스코드

n = int(input())
dp = [1] * 117
for i in range(4, n+1):
    dp[i] = dp[i-3] + dp[i-1]
print(dp[n])

문제풀이

1. n을 입력받는다.

2. 자연수 n의 범위가 n <= 116 이므로 크기가 117이고 1로 된 리스트를 생성한다.

3. i == n이 될 때까지 반복문을 이용하여 순차적으로 값을 구하고 리스트에 저장한다.

4. 해당하는 수를 출력한다