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

https://www.acmicpc.net/problem/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 = int(input())
li = [0] * (n + 1)

for i in range(1, n + 1):
    if i in [1, 2, 3]:
        li[i] = 1
    else:
        li[i] = li[i - 1] + li[i - 3]
        
print(li[n])

 

n을 입력받은 후 li를 0으로 초기화하고, 문제에 주어진 피보나치 규칙에 의해 bottom-up 방식으로 구하면 된다.

다만 만약 li를 1로 초기화했다면 1, 2, 3에 대해 예외처리할 필요가 없기 때문에 코드가 더 간결해질 것이다!