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

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

import sys

# with open("./data.txt", "r") as file:
#     def input():
#         return file.readline().strip()

def input():
    return sys.stdin.readline().strip()
    
    
N = int(input())
dp = [1] * (N + 1)

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

print(dp[N])

---

기본 피보나치 구현과 똑같이 하되 호출 횟수를 구해야 하기 때문에
dp[n-1] + dp[n-2] + 1을 해서 호출 횟수를 하나씩 늘려주면 된다.

아래처럼 1로 초기화 한 이유는 input 값이 0이 들어오면 index 에러가 발생하기 때문이다.

그러면 (dp[i-1] + dp[i-2] + 1) 할 때 값이 안맞을 것 같지만
어차피 dp[i]는 안사용하고 이전 값들을 사용하기 때문에 상관없다.

dp = [1] * (N + 1)


// N=0이면 index 에러
dp[0] = 1
dp[1] = 1