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])