[Python] 프로그래머스 피보나치 수 | DP

 

~목차~

문제

문제 해결 포인트

작성 코드

---

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12945

프로그래머스

 

 

문제 해결 포인트

- 전형적인 DP(Dynamic Programming, 다이나믹 프로그래밍) 문제

   한 번 계산한 결과에 대해 저장해두어 이후 다시 계산하지 않는다

 

- 0 ~ n 피보나치 수를 저장할 리스트 선언 후 0과 1에 대하여 초기값 설정

- 2 ~ n까지 f(n) = f(n-1) + f(n-2)를 수행

- dp[n]을 반환하되 1234567로 나눈 나머지로 반환 주의

 

작성 코드

def solution(n):
    dp = [0]*100001
    dp[1] = 1
    
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    
    return dp[n] % 1234567

 

 

 

도움이 되셨다면 좋아요 눌러주세요💚