[백준_17175] 피보나치는 지겨웡~ python

시간이 없어서 급하게 풀다가

자기 자신의 호출 횟수 1을 더해줘야 한다는 것을 까먹었다.

f(i) = f(i-2) + f(i-1) + 1이다

# fib 설계
fib = [
    0 for _ in range(51)
]

# fib 초기설정
fib[0] = 1
fib[1] = 1
fib[2] = 3
fib[3] = 5

# fib 채워넣기
for i in range(4, 51):
    fib[i] = fib[i-2] + fib[i-1] + 1

# n 입력
n = int(input())

# 출력
print(fib[n] % 1000000007)