[알고리즘][Python] 백준(BOJ) 1788 피보나치 수의 확장_파이썬

 

1788 피보나치 수의 확장    www.acmicpc.net/problem/1788

1788번: 피보나치 수의 확장

 

 

 

문제 풀기 전 공부할 것 : 수학, 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• n을 양수, 0, 음수일 때 나눠서 계산한다.
• n이 양수일 때, 1, 1, 2, 3, 5, 8, 13, ... 으로 피보나치 수이다.
• n이 음수일 때, 1, -1, 2, -3, 5, -8, ... 으로 피보나치 수이다.
• n이 양수라고 가정하고 피보나치 배열을 구한다.
• n이 음수일 때 그리고 2로 나누어 떨어진다면 첫 줄에 -1을 출력하고 아니라면 1을 출력한다.

 

 

<코드>

n = int(input())
flag = 0
if n > 0:
    flag = 1
elif n < 0:
    flag = -1
    
dp = [0, 1]
for _ in range(2, abs(n)+1):
    dp.append((dp[-1]+dp[-2])%1000000000)

if flag == -1:
    if (-n) % 2 != 0:
        flag = -flag

print(flag)
print(dp[abs(n)])