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

🥚문제

---

🥚입력/출력

---

🍳코드

import sys
input = sys.stdin.readline

n = int(input().strip())

# dp[n][0] = n번째 줄에 사자가 없음
# dp[n][1] = n번째 줄의 왼쪽에 사자 배치
# dp[n][2] = n번째 줄의 오른쪽에 사자 배치
dp = [[0, 0, 0] for _ in range(n+1)]

for i in range(1, n+1):
    if i == 1:
        dp[1][0] = 1
        dp[1][1] = 1
        dp[1][2] = 1
    else:
        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

# dp[n]의 합이 9901을 초과할 수 있으므로 마지막에 한 번 더 연산!!!
print(sum(dp[n]) % 9901)

---

🧂아이디어

DP

• 사자를 가로로도 세로로도 붙어 있게 배치할 수는 없으므로 한 행에 넣을 수 있는 사자는 0마리 or 1마리

• 한 행에 사자를 넣는 경우를 세가지로 나누어 생각할 수 있다.
  1. 한 행에 사자가 한 마리도 없음
  2. 한 행의 왼쪽 열에 사자가 한 마리 있음
  3. 한 행의 오른쪽 열에 사자가 한 마리 있음

• 이를 아래와 같이 표현할 수 있다.

  • dp[n][0] = n번째 row에 사자가 없음
  • dp[n][1] = n번째 row의 왼쪽에 사자
  • dp[n][2] = n번째 row의 오른쪽에 사자

• dp[n][0]

  • n-1번째 row에 사자가 없을 때,
    n-1번째 row의 왼쪽에 사자가 있을 때,
    n번째 row의 오른쪽에 사자가 있을 때 모두 가능하다.
  • dp[i][0] = (dp[i-1][0] + dp[i-1][1] + dp[i-1][2]) % 9901

• dp[n][1]
  • n-1번째 row에 사자가 없을 때,
    n-1번째 row의 오른쪽에 사자가 있을 때 가능하다.
  • dp[i][1] = dp[i-1][0] + dp[i-1][2] % 9901

• dp[n][2]
  • n-1번째 row에 사자가 없을 때,
    n-1번째 row의 왼쪽에 사자가 있을 때 가능하다.
  • dp[i][2] = dp[i-1][0] + dp[i-1][1] % 9901

매우 참고: https://mygumi.tistory.com/128

---

🧐

• 마지막에 print(sum(dp[n]) % 9901) dp[n]의 sum을 출력할 때, 9901 나머지 연산을 빼먹으면 안된다! sum이 9901을 넘을 수도 있기 때문에 반드시 나머지 연산을 해줘야 통과할 수 있다.