[알고리즘/백준] 1309: 동물원(python)

두개의 방법이 있다.

1. 규칙을 찾기
0 1 2 3 4
1 3 7 17 41
보면 dp[i] = dp[i-1] * 2 + dp[i-2]
이런 규칙이 있다.

N = int(input())
dp = [1, 3] + [0] * N

for i in range(2, N+1):
    dp[i] = (dp[i-1] * 2 + dp[i-2]) % 9901
print(dp[N])

하지만 이렇게 풀면 어려운 dp문제 풀기가 불가능하다.

2. 이전 경우 사용하기

이전 경우를 사용해야한다... 현재 내가 선택할 수 있는 경우는
1. 사자를 넣지 않는 경우
2. 왼쪽에 넣는 경우
3. 오른쪽에 넣는 경우
세가지가 있다.

사자를 넣지 않으면 이전 칸에 경우들 중에 가능한 경우가 1, 2, 3 다 가능핟.
사자를 왼쪽에 넣으면 넣지 않는 경우, 오른쪽에 넣는 경우 2가지가 가능하고
사자를 오른쪽에 넣으면 넣지 않는 경우, 왼쪽에 넣는 경우 2가지가 가능하다.

이를 점화식으로 써보면
0 = 넣지 않는 경우, 1 = 왼쪽, 2 = 오른쪽
dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-2][2]
dp[i][1] = dp[i-1][0] + dp[i-1][2]
dp[i][2] = dp[i-1][0] + dp[i-1][2]

N = int(input())
dp = [[1, 1, 1] for _ in range(N+1)]
for i in range(2, N+1):
    dp[i][0] = (dp[i-1][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] = (dp[i-1][0] + dp[i-1][1]) % 9901
print(sum(dp[N]) % 9901)