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은 음수로 주어질 수도 있다.
코드
N = int(input())
arr = [0, 1]
for i in range(2, abs(N) + 1):
arr.append((arr[i-1] + arr[i-2]) % 1000000000)
if N < 0:
if abs(N) % 2 == 0:
print(-1)
else:
print(1)
elif N > 0:
print(1)
else:
print(0)
print(arr[abs(N)])한마디
음수의 피보나치를 어떻게 처리해야할까 걱정했는데 노트에 적어보니 양수의 피보나치와 값은 똑같았다. n이 짝수인지 홀수인지에 따라 부호만 달라지는 것을 알 수 있었다.
