문제
https://www.acmicpc.net/problem/17175
접근
- 출력을 1000000007로 나눈 나머지로 하라는 것은 피보나치 함수 호출의 숫자가 1억보다 큰값이 존재한다는 뜻이므로, 실제로 피보나치 함수를 구현해서 호출 횟수를 세는 방법은 시간초과가 난다. (제한시간 1초)
- 어떠한 값 i에 대한 피보나치 함수 호출 횟수는 i-1의 피보나치 함수 호출 횟수와 i-2의 피보나치 함수 호출 횟수의 합이므로 다이나믹 프로그래밍으로 접근
풀이
- dp[i]를 i에 대한 피보나치 함수 호출 횟수로 정의
- 점화식: dp[i] = dp[i - 1] + dp[i - 2]
- 자기 자신의 숫자에 대한 함수 호출이 존재하므로, dp 배열의 전체 값은 1로 초기화
n = int(input())
dp = [1] * (n + 1)
for i in range(2, n + 1):
dp[i] += (dp[i - 1] + dp[i - 2]) % 1000000007
print(dp[n])
'Python > Coding Test' 카테고리의 다른 글
16960 스위치와 램프 (0) | 2022.02.13 |
---|---|
1781 컵라면 (0) | 2022.02.10 |
15918 랭퍼든 수열쟁이야!! (0) | 2022.02.09 |
11411 합 구하기 (0) | 2022.02.09 |
13702 이상한 술집 (0) | 2022.02.08 |