백준 / 동물원 / 1309번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 동물원 / 1309번 (실버 1단계)

문제 사이트: https://www.acmicpc.net/problem/1309

 

문제 설명

---

나의 풀이

def solution(n):
    dp = [0] * (n + 1)
    dp[1] = 3

    if n > 1:  # 초기값
        dp[2] = 7

    for i in range(3, n + 1):
        dp[i] = (dp[i - 1] * 2 + dp[i - 2]) % 9901  # Dp

    return dp[n]  # 결과 값


def main():
    n = int(input())  # 케이지 수

    print(solution(n))


if __name__=="__main__":
    main()

---

※ 알아야 할 것

동적 계획법을 이용한 점화식을 세우면 해결할 수 있습니다!

걸린 시간: 40:52

지연된 이유: n = 3 과정 값을 잘못 도출해서 점화식을 다시 세우는데 시간이 많이 소요됐다.