[python] 백준 1788 피보나치 수의 확장

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

1788번: 피보나치 수의 확장

 

문제해결

• |n| >1 일 때 F[n] = F[n-1] + F[n-2] 를 이용해서 새로운 수를 F 리스트에 넣는다.
• n을 음수로 확장시켰으 때 놀라운 규칙을 알면 끝이다.

음수와 양수의 절대값이 같을 때 피보나치 값도 절대값이 같다. 그리고 음수일 때 인덱스 짝수영역은 음수 홀수 영역은 양수이다.

CODE

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