BOJ 17175

Input

Default

import sys
sys.setrecursionlimit(100000)
input = sys.stdin.readline

fibonacci 함수에 인자로 입력할 n이 주어진다. (0 ≤ n ≤ 50)

n = int(input())

Output

fibonacci 함수가 호출된 횟수를 출력한다.

출력값이 매우 커질 수 있으므로 정답을 1,000,000,007 로 나눈 나머지를 출력한다.

if n < 2: print(num[n])
else:
  print(num[n] % 1000000007)

DP

• 일단 호출 횟수 를 출력해야 한다는 점!

• 재귀함수를 사용하면 피보나치 수열을 진행하는 동시에 count도 해야하므로 시간 초과 가 발생한다…

• 따라서 배열 을 사용해서 count 횟수만 진행한다! 이러면 for문으로 충분함

  num = [1, 1]

1. n < 2 인 경우에는 위에서 바로 출력하면 됨

   if n < 2: print(num[n])

2. 그 외의 경우에는 배열을 증가시키고 출력해야 함

   • 횟수는 default로 n < 2 의 경우에는 1번 이고, 그 이후에는 fibonacci(n-2) + fibonacci(n-1) 에 따라 num[본인-1] + num[본인-2] + 본인 호출 횟수 1 을 append 한다.

   else:
     for _ in range(n-1):
       # fibonacci(n-2) + fibonacci(n-1)에 자기 자신 호출 횟수 +1
       num.append(num[-1] + num[-2] + 1)
     
     print(num[n] % 1000000007)