[DP/동적계획법] 백준 1788 피보나치 수의 확장 - 파이썬(Python)

[ Contents ] 1. 문제 (링크 참조) 1788번: 피보나치 수의 확장 첫째 줄에 F(n)이 양수이면 1, 0이면 0, 음수이면 -1을 출력한다. 둘째 줄에는 F(n)의 절댓값을 출력한다. 이 수가 충분히 커질 수 있으므로, 절댓값을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 풀이 피보나치의 '음수 부분'을 구하는 문제입니다. 본래, 피보나치는 n = 2부터 시작하죠. n = 1일 때, f(1) = f(0) + f(-1) 이므로 f(-1) = f(1) - f(0) = 1 피보나치의 정의를 역이용하면, f(-1)도 구할 수 있습니다. 즉, 음수 부분을 구할 때에는 조금 식이 달라집니다. f(n-2) = f(n) - f(n-1) f(-1) = f(1..

원문링크 : [DP/동적계획법] 백준 1788 피보나치 수의 확장 - 파이썬(Python)