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

문제

• fibonacci 를 재귀로 구현했을 때, fibonacci(N) 를 입력 시 fibonacci 함수가 호출되는 횟수 계산하기
  • 0 <= N <= 50

 

풀이

• DP
  • DP[n] : fibonacci(n) 을 입력했을 때 fibonacci 함수가 호출되는 횟수
• fibonacci(n) 을 입력하면서 fibonacci 가 호출되고, fibonacci(n-1) 과 fibonacci(n-2)가 각각 호출된다.
  • 이때, fibonacci(n-1) 의 호출 횟수와 fibonacci(n-2)의 호출횟수를 함께 더해주면 된다.
  • dp[n] = dp[n-1] + dp[n-2] + 1
• N의 범위가 0부터 이므로 dp 테이블 인덱스 범위 주의해야 한다!

 

N = int(input())
# dp[n] : fibonacci(n) 입력했을 때 fibonacci 호출 횟수
dp = [0] * (N+1)

dp[0] = 1 
if N > 0:   # N 인덱스 범위 생각!
    dp[1] = 1

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

print(dp[N] % 1_000_000_007)

 

References

• 백준 17175번
• 2023.04.25 오늘의 문제