[알고리즘] 백준 1788 파이썬 - 피보나치 수의 확장

 

1788번: 피보나치 수의 확장

 

문제

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 F(n)은 0 이상의 n에 대해서만 정의된다.

하지만 피보나치 수 F(n)을 n이 음수인 경우로도 확장시킬 수 있다. 위의 식에서 n > 1인 경우에만 성립하는 F(n) = F(n-1) + F(n-2)를 n ≤ 1일 때도 성립되도록 정의하는 것이다. 예를 들어 n = 1일 때 F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1)은 1이 되어야 한다.

n이 주어졌을 때, 피보나치 수 F(n)을 구하는 프로그램을 작성하시오. n은 음수로 주어질 수도 있다.

 

문제풀이

 

arr=[0,1]
n=int(input())
#01
for i in range(2,abs(n)+1):
    arr.append((arr[i-1]+arr[i-2])%1000000000)
#02
if n%2==0 and n<0:
    print(-1)
elif n==0:
    print(0)
else:
    print(1)
#03
print(arr[abs(n)])

- #01 : 2부터 n까지 피보나치 값을 리스트에 추가한다.

- #02 : 음수이면서 짝수이면 -> 음수, 0이면 0, 나머지는 양수로 각각 출력해준다.

- #03 : n번째 피보나치 수를 출력해준다.