[99클럽 코테 스터디 2일차 TIL] 백준 14495 피보나치 비스무리한 수열

오늘의 학습 키워드

피보나치 수열

공부한 내용 본인의 언어로 정리하기

문제

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

코드

n = int(input())
a = [0] * (n+1)
if n == 1 or n == 2 or n == 3:
    print(1)
    exit()
else:
    a[1] = 1
    a[2] = 1
    a[3] = 1
    for i in range(4, n+1):
        a[i] = a[i-1] + a[i-3]
    print(a[n])

n = int(input())
a = [0] * 116
a[0] = 1
a[1] = 1
a[2] = 1
for i in range(3, n):
    a[i] = a[i-1] + a[i-3]
print(a[n-1])

 

첫 번째 코드는 a 리스트를 입력만큼 할당한 후 a==1, 2, 3, 4 이상일 경우를 나누어 계산하였다.

두 번째 코드는 입력값이 최대 116이라고 했음으로 처음부터 116만큼 리스트를 할당 후 바로 피보나치 계산을 수행하였다. 

오늘의 회고

피보나치 수열

피보나치 수열(Fibonacci Sequence)은 이전 두 항의 합으로 다음 항을 구하는 수열

F(n) =  
    0  if n == 0  
    1  if n == 1  
    F(n-1) + F(n-2)  if n ≥ 2

 

첫 번째와 두 번째 값은 각각 0과 1이며, 이후의 값은 앞의 두 값을 더한 것으로 큰 값까지 계산