동물원 Post

layout: post title: 동물원 author: Jaeheon Kwon categories: PS tags: [dp]

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

솔직히 만만하게 봣는데 점화식 세우는거 실패했다. 결국솔루션 봤는데…나중에 다시 풀어봐야겠다.

n = 0일 때 즉, 아무 우리가 없을 때는 사자를 놓지 않는 경우이므로 1가지 경우이다.

n = 1일 때는 이전의 경우인 n=0(사자를 놓지 않는 경우) + 왼쪽칸에 놓는 경우 + 오른쪽 칸에 놓는 경우 = 3이다.

n = 2일 때는 사자를 놓지 않는 경우가 n=1일때의 케이스가 된다. (1번라인에만 두고 2번 라인은 빈 상태)

사자를 놓는 경우는 2번 라인에 왼쪽, 오른쪽에 두는 경우와 두마리씩 두는 경우 2가지를 합쳐서 총 4개가 된다.

즉, n = 2일때는 7이다.

사자가 있는경우, 없는 경우로 나눠서 이를 더하는 식의 점화식을 세울 수 있다.

dp[i] = (dp[i-2] *3 + (dp[i-1]-dp[i-2]) * 2)

n = int(input())
dp = [1 for _ in range(n+1)]
dp[1] = 3
if n==1:
    print(dp[1])
else:
    for i in range(2, n+1):
        dp[i] = dp[i-2] + (dp[i-1]*2)
        dp[i] %= 9901
    print(dp[n])