백준 1309: 동물원

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

이번에 풀어본 문제는 "백준: 동물원(1309)"입니다. 문제를 읽어보면 직관적으로 dp문제라는 것을 알 수 있었습니다.

 

그렇다면 문제 풀이의 핵심은 다름 아닌 핵심 규칙(점화식)을 찾는 것인데요, 문제에서 주어진 규칙을 보면 열은 2열로 고정되어 있고, 행(n)이 주어지는 형태입니다. 그렇다면 한 행이 늘어날 때마다의 규칙을 찾아서 점화식을 세워주면 되겠네요. 점화식을 세우기 전,

 

1) 가로로 사자를 배치하면 안 된다.

2) 세로로 사자를 배치하면 안 된다.

3) 사자를 배치하지 않는 경우도 한 가지 경우로 친다.

 

이 세 가지 조건을 생각해야 합니다. 따라서 위 조건들에 따라서 dpLi[n][0]을 n행에 사자를 아예 배치하지 않는 경우, dpLi[n][1]을 n행의 왼쪽에만 사자를 배치할 경우, dpLi[n][1]을 n행의 오른쪽에만 사자를 배치할 경우로 나누어서 생각해주고 점화식을 세웁니다.

 

dpLi[n][0] = dpLi[n-1][0] + dpLi[n-1][1] + dpLi[n-1][2]

dpLi[n][1] = dpLi[n-1][0] + dpLi[n-1][2]

dpLi[n][2] = dpLi[n-1][0] + dpLi[n-1][1]

 

이렇게 나타낼 수 있겠죠. 하지만 여기서 또 중요한 점은 경우의 수를 9901로 나눈 나머지로 나타내야 하는 것이기 때문에, 각각의 경우에 MOD(9901로 나누어준 나머지)를 계산해서 dpLi에 저장해주어야 합니다.

따라서 코드는 다음과 같습니다.

 

from sys import stdin

MOD_KEY = 9901  # 나누어 줘야하는 수(9901)

n = int(input())
dpLi = [[0,0,0] for _ in range(n+1)]

for i in range(3):
    dpLi[1][i] = 1

for i in range(2, n+1):
    dpLi[i][0] = (dpLi[i-1][0] + dpLi[i-1][1] + dpLi[i-1][2]) % MOD_KEY
    dpLi[i][1] = (dpLi[i-1][0] + dpLi[i-1][2]) % MOD_KEY
    dpLi[i][2] = (dpLi[i-1][0] + dpLi[i-1][1]) % MOD_KEY

# 결과도 MOD_KEY로 나눠주어야 함
answer = sum(dpLi[n]) % MOD_KEY

print(answer)