[백준][1788] - 피보나치 수의 확장 - python 파이썬

피보나치 수의 확장 - 1788

1788번: 피보나치 수의 확장

성능 요약

메모리: 71248 KB, 시간: 212 ms

분류

다이나믹 프로그래밍, 수학

문제 설명

수학에서, 피보나치 수는 위의 점화식과 같이 귀납적으로 정의되는 수열이다. 위의 식에서도 알 수 있듯이, 피보나치 수 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이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다.

---

🙋 문제 해석

먼저 이 문제를 풀기 전에는 다이나믹 프로그래밍이나 피보나치를 아시고 푸시는게 도움이 됩니다.

 

물론 재귀적으로도 풀어도 되지만 다른 어러운 문제를 풀기 위해선 DP를 사용하시라고 권장드리고싶습니다

수에 따라서 10배 이상 차이나는 경우가 있습니다.

시간 차이가 많이 나는 걸 볼 수 있습니다. (메모리는 PyPy를 써서그렇습니다..)

한 번으로 코딩 역량을 향상하는 동적프로그래밍 기법을 알아보자! 🔥

DP와 피보나치의 관해 간략하게 설명한 글입니다.

 

 

 

점점 늘어나는 수를 두 가지 경우를 생각하면서 푸시면 되는데요.

 

 

 

저는 양수와 음수를 구분하여 풀었습니다.

 

IF 양수 :
    F[5] = F[4] + F[3]

 

여기까지는 이해하실 수 있지만,(이해가 안가면 위에 링크 한 번 봐주시면됩니다!)

 

 

 

음수의 경우에는 다른데요. 문제에서 상술하듯이.

 

F(1) = F(0) + F(-1)이 성립되어야 하므로, F(-1) 1이 되어야한다.

 

F(1)을 이용해서 F(-1)을 구했는데요,

 

여기에 집중했습니다.

 

 

 

 

 

 

 

만약 내가 구하고 싶은 값이 F[-2] 라면?

F[0] = F[-2] + F[-1]

F[-2] = F[-0] - F[-1]

 

항을 이동함으로써 문제를 쉽게 풀 수 있습니다.

 

이제 n이 양수인지 음수인지 확인하고 문제를 푸시면 됩니다!!

---

🔑 Solution 🔑

import sys
input = sys.stdin.readline
def dp(n):
    if n == 0:
        return 0
    elif n > 0:
        dp_list = [0, 1]
        for i in range(2, n + 1):
            dp_list.append((dp_list[i - 1] + dp_list[i - 2]) % 1000000000)
        return dp_list[n]
    else:
        dp_list = [0, 1, -1]
        for i in range(3, -n + 1):
            dp_list.append((dp_list[i - 2] - dp_list[i - 1]) % 1000000000)
        return dp_list[-n]

n = int(input())
res = [0, 0]
res[1] = dp(abs(n))
if n > 0:
    res[0] = 1
elif n < 0:
    if abs(n) % 2 == 0:
        res[0] = -1
    else:
        res[0] = 1
else:
    res[0] = 0

print(res[0])
print(abs(res[1]))

---

🙇