[14495] 피보나치 비스무리한 수열 in python

 

다이나믹 프로그래밍 기법을 사용하여

푸는 피보나치 수열 문제

 

시간은 68 ms 나옴!

 

n이 3 이하면 1을 출력하고 프로그램 종료

n이 4 이상이면 피보나치 수열 기법을 적용한다.

 

 

n = int(input())
if n < 4:
    print(1)
    exit()
else:
    f = [0 for _ in range(n + 1)]
    for i in range(1, 4):
        f[i] = 1
    for i in range(4,n+1):
        f[i]=f[i-1]+f[i-3]
    print(f[n])

---

코드 양을 좀 줄여봄!

 

배열의 크기를 미리 주어진 최대 크기만큼 잡아주고 시작함!

그러면 for문을 덜 돌려도 되고

if else문을 쓸 필요가 없음!

f = [0 for _ in range(117)]
f[1], f[2], f[3] = 1, 1, 1
n=int(input())
for i in range(4, n + 1):
    f[i] = f[i - 1] + f[i - 3]
print(f[n])