1309. 동물원

문제

풀이

다이나믹 프로그래밍 방법으로 풀어야 한다.
3가지 경우가 있다.

1. 오른쪽에 있을 경우
2. 왼쪽에 있을 경우
3. 아무것도 없을 때

N = 1일 때 생각해보자
dp[0][0] => 왼쪽에 있을 때 하나만 가능하다. = 1
dp[0][1] => 오른쪽에 있을 때 하나만 가능하다. = 1
dp[0][2] => 왼쪽 오른쪽 둘 다 없을 때 하나만 가능하다. =1

N = 2일 때 생각해보자
dp[1][0] => 왼쪽에 있을 경우 dp[0][1](이전에서 오른쪽에 있을 경우) + dp[0][2](이전에서 아무것도 없을 경우)
dp[1][1] => 오른쪽에 있을 경우 dp[0][0](이전에서 왼쪽에 있을 경우) + dp[0][2](이전에서 아무것도 없을 경우)
dp[1][2] => 아무것도 없을 경우 (dp[0][0] + dp[0][1] + dp][2])이전 모든 경우의 수이다.

즉 점화식으로 나타내면 다음과 같다.
dp[n][0] = dp[n-1][1] + dp[n-1][2]
dp[n][1] = dp[n-1][0] + dp[n-1][2]
dp[n][2] = dp[n-1][0] + dp[n-1][1] + dp[n-1][2]

for test_case in range(1):
    n = int(sys.stdin.readline())
    dp = []
    for _ in range(n):
        dp.append([0,0,0])
    dp[0][0], dp[0][1], dp[0][2] = 1, 1, 1

    for i in range(1, n):
        dp[i][0] = (dp[i-1][1] + dp[i-1][2]) % 9901
        dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % 9901
        dp[i][2] = sum(dp[i-1]) % 9901

    print(sum(dp[-1]) % 9901)