[백준/Python]15624번: 피보나치 수 7 (DP)

1. 문제 

15624번: 피보나치 수 7

 

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

 

4. 잊지말자 

 

많이 헤멨던 문제다. 

 

DP를 배우기 전 그냥 재귀호출로만 풀다가 시간초과, 런타임 에러를 띄우고.. DP를 배우고 다시 돌아왔다. 

하지만 메모리 초과 .. 메모이제이션에서 배열이 문제였다. 너무 많은 배열에 너무 큰 숫자를 집어넣는다는 것.. 

 

메모이제이션 방법을 살짝 바꾸어보았다. 처음부터 0으로 할당하지 말고 .append()함수를 이용하여 붙이는 방식으로 

(이게 큰 효과를 보았는지는 사실 잘 모르겠다. 이것보단 나눈 값을 배열에 넣은 것이 정답에 가까워졌다고 생각한다. ) 

 

그리고 100번째, 10000번째 피보나치 수를 바로 배열에 넣는 것이 아닌 나눠준 값을 바로 배열에 넣었다. 

그럼 값이 확 줄어들겠죠? 

 

그래서 이번 문제에서 느낀 점은 문제에서 '구하라고 하는 값'에 집중하자였다. 

우리는 1,000,000,007을 나눈 나머지만 구하면 되는데 당장 fib(1000)만 구해도 어마무시한 값이 나온다.. 

 

그러니 괜히 쓸데없이 큰 값을 구해서 나머지를 구하는데에 힘 빼지 말고 작게작게, 잘게잘게 넣어주자 ~