[BOJ] 1309번 - 동물원

---

문제설명

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

1309번: 동물원

사고과정

• 타일 공사같은 DP 유형의 문제인가 생각했다. 우선은 N = 3일 떄까지 경우의 수를 연습장에 그려보았다. 타일 공사 문제에서 얻은 인사이트를 가지고 적용해보았다. 서로 사자들이 가로, 세로로 붙어있으면 안된다는 조건을 만족시켜야 한다! 
• N이 1개씩 늘어남에 따라 마지막 줄 N by 2 칸의 입장에서 살펴보면 알 수 있다. 즉, 마지막  N번째 줄 2칸 중 왼쪽 칸만 채워져 있다면 N-1번째 줄에는 오른쪽 칸만 채워져 있거나 아무 칸에도 사자가 없어야 한다.(문제에서 아무 칸에 사자가 없어도 괜찮다고 했다) 반대로 N번째 줄 2칸 중 오른쪽 칸만 사자가 채워져 있다면 N-1번째 줄 칸에는 왼쪽 칸에만 사자가 있거나 아무 칸에도 사자가 없어야 한다.
• 따라서 이를 2차원 리스트 DP 테이블로 정의한다. 행에는 N을, 열은 N번째 줄에 사자를 어느 칸에 채워놓는지에 대한 의미이다. 0은 왼쪽 칸에 사자를, 1은 오른쪽 칸에 사자를, 2는 아무칸에도 사자를 넣지 않은 것을 의미한다. 그리고 N = 1일땐 각각 1가지 경우밖에 없으므로 DP 테이블을 초기화시켜준다. 그리고 다음과 같은 점화식을 세울 수 있다.
• DP 테이블의 $i$번째 행 열($j$)값이 0(왼쪽 칸) 이라면 DP 테이블 이전 행($i-1$)의 1(오른쪽 칸)과 2(아무칸에도 사자 없음)값을 더해준다. 단, 아무칸에도 사자가 없는 경우는 이전 행의 모든 값을 더해준다. 따라서 아래 소스코드처럼 점화식을 세워줄 수 있다.
• 단, 주어진 데이터 범위가 10만으로 작지는 않기 때문에 DP 테이블을 갱신해줄 때, 문제에서 주어진 것처럼 9901로 나누면서 업데이트 해주자. 만약 안해주면 메모리 범위를 초과하게 된다.

풀이

import sys
input = sys.stdin.readline
n = int(input())
mod = 9901
dp = [[1, 1, 1] for _ in range(n)]

for i in range(1, n):
    for j in range(0, 3):
        # 왼쪽 칸
        if j == 0:
            dp[i][j] = dp[i-1][j+1] + dp[i-1][j+2]
            dp[i][j] %= mod
        # 오른쪽 칸
        if j == 1:
            dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]
            dp[i][j] %= mod
        # 아무 칸도 안채웠을 때
        if j == 2:
            dp[i][j] = sum(dp[i-1])
            dp[i][j] %= mod

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