[백준/1309/파이썬] 동물원 - DP

---

소스코드

n = int(input())

dp =[1,3,7]

for i in range (2,100001):

  dp.append((dp[i]*2 + dp[i-1])%9901)

print(dp[n]%9901)

---

알고리즘

점화식 (dp[i]*2 + dp[i-1])만 찾으면 쉽게 풀리는 문제였다.

다만 처음에 메모리초과 에러가 났는데 찾아보니 계산할때마다 9901의 나머지를 추가해줘야 했다.

나머지로 계산을 해도 전체 결과에서 나머지 계산을 한게 같게 되는걸 알게 되었다.