알고리즘/python
[python/파이썬] 백준 17175 피보나치는 지겨웡~
ㅌㅇㄴ
2022. 7. 14. 15:31
반응형
[문제 출처]
https://www.acmicpc.net/problem/17175
17175번: 피보나치는 지겨웡~
혁진이는 알고리즘 문제를 만들라는 독촉을 받아 스트레스다. 하지만 피보나치 문제는 너무 많이 봐서 지겹기 그지없다. 그러나 문제를 만들 시간이 없는 혁진이는 피보나치 문제를 응용해서
www.acmicpc.net
[문제 풀이]
dp[i] 는 dp[i-1] 와 dp[i-2]의 합보다 1 큰 수로 정해진다.
fibonacci(n)을 호출했을 때 1혹은 0이 나올 때까지 fibonacci(n-1)과 fibonacci(n-2)를 호출한다.
따라서 fibonacci(n)를 호출한 횟수 1과 fibonacci(n-1)을 호출했을 때 fibonacci 호출 횟수인 dp[n-1]과
fibonacci(n-2)을 호출했을 때 fibonacci 호출 횟수인 dp[n-2]을 더해줘야 한다.
import sys
input = sys.stdin.readline
n = int(input())
dp = [1 for _ in range(n+1)]
for i in range(2, n+1):
dp[i] = (dp[i-1] + dp[i-2] + 1)%1000000007
print(dp[n])
반응형