Koala - 10기/코딩테스트 준비 스터디
[백준/Python]15624번: 피보나치 수 7
쥬발이
2023. 3. 19. 14:30
1. 문제
15624번: 피보나치 수 7
첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.
www.acmicpc.net
2. 해결
사실 해결 방법은 단순했다.
- DP를 사용해자.
- [ 알고리즘 ] 다이나믹 프로그래밍(DP) - 개념
- 문제에서 '구하라는 값'에 집중하자 → 나머지 값을 메모이제이션에 넣어보자 ~
3. 코드
n = int(input())
dp= [0,1,1]
for i in range(3,n+1):
dp.append((dp[i-1]+dp[i-2])%1000000007)
print(dp[n])