[파이썬] 백준 8394 : 악수

[파이썬] 백준 8394 : 악수

https://www.acmicpc.net/problem/8394

8394번: 악수

실버 4

수학, DP

---

접근

하나하나 경우의 수를 직접 계산해보면 피보나치 수열로 규칙이 나타난다는 것을 알 수 있다.

문제는 n의 범위가 어마어마하기 때문에 수가 커지면 커질수록 다루는 수가 기하급수적으로 증가한다는 점이다.

시간 초과하지 않으려면 구한 값의 마지막 자리를 미리 넣어주는 방법을 이용해야 했다.

 

코드

import sys
n = int(sys.stdin.readline())
dp = [1] * (n+1)
for i in range(2, n+1):
    dp[i] = (dp[i-1] % 10 + dp[i-2] % 10) % 10
print(dp[-1])

 

어차피 일의 자리 수만 구하면 되기 때문에 피보나치 수열로 구한 값을 처음부터 일의 자리만 리스트에 넣어주도록 했다. 

그냥 값을 박아버리면 각 인덱스에 들어가는 수가 어마어마하게 커져서 메모리 초과가 난다.

 

마지막 dp[-1]로 출력하는 부분을 dp[n]으로 출력해도 상관없는데 dp[n]의 경우가 살짝 더 빠르게 나왔다.