[백준][Python] 17175번 피보나치는 지겨웡~ - 코팩

https://www.acmicpc.net/problem/17175

17175번: 피보나치는 지겨웡~

풀이

피보나치의 함수가 얼마나 호출되는지에 대한 계산을 요구한다.

그래서 dp테이블을 만들어서 n이 0~2까지의 함수 호출 횟수를 넣어준 뒤 다이나믹 프로그래밍을 통해서 n이 원하는 답을 구해주었습니다.

 

코드

# 17175번 피보나치는 지겨웡~
n = int(input())
dp = [1,1,3]
for i in range(3, n+1):
    dp.append((dp[i-1] + dp[i-2] + 1)%1000000007)

print(dp[n])

 

출력결과