[BOJ_1788/Python] 피보나치 수의 확장

문제

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은 음수로 주어질 수도 있다.

입력

첫째 줄에 n이 주어진다. n은 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

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

---

풀이

음수 수열이 양수 수열과 부호가 다른 것 말고는 차이가 없다.

양수 수열 : 0, 1, 1, 2, 3, 5, ...

음수 수열 : 0, 1, -1, 2, -3, 5, ...

양수와 음수 동일한 방법으로 dp 테이블을 초기화했고 n이 음수인 경우 양수인지 짝수인지를 검사해서 정답을 출력했다.

# 입력
n = int(input())

# 풀이
if n == 0:
    print(0, 0, sep='\n')
    exit()

dp = [0 for _ in range(1 + abs(n))]
dp[0], dp[1] = 0, 1

for i in range(2, len(dp)):
    dp[i] = (dp[i-1] + dp[i-2]) % 1000000000

# 출력
idx = abs(n)
answer = -dp[idx] if n < 0 and n % 2 == 0 else dp[idx]

print(1 if answer > 0 else -1)
print(abs(answer))