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

goblin·2021년 9월 18일
1

알고리즘

목록 보기
11/12

BOJ 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번째 피보나치 비스무리한 수열을 구해보자!

제출 코드

d=[0]*117

d[1]=1
d[2]=1
d[3]=1

n=int(input())

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

    
print(d[n])

풀이

이 문제는 정말 기본적인 다이나믹 프로그래밍 문제이다.
처음에 테이블을 초기화 할 때 범위를 잘못 설정해서 런타임 에러가 났다..ㅎㅎ
풀고나서 보니까 초기화할 때 굳이 0으로 하지 않고 전체를 1로 초기화해도 풀렸을 것 같다!

0개의 댓글