1309.md

백준 1309번 동물원

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

---

코드 설명

• 사자를 배치할 때 상하좌우 연속되게 배치를 못하기 때문에 경우의 수를 구하면 3가지로 좁힐 수 있다.
  • 아예 배치를 하지 않는다.
  • 왼쪽에 배치한다.
  • 오른쪽에 배치한다.
• 그러면 가장 먼저 dp[1]을 채울 수 있게 되는데 각각 1이 된다는 사실을 알 수 있다. -> 아예 배치하지 않거나 왼쪽에 한마리 놓거나 오른쪽에 한 마리 놓는 경우의 수를 다 합하면 3이 된다.
• 따라서 2차원 리스트를 만든 뒤 dp[a][b] a에는 n만큼의 행을 b에는 왼쪽 없음 오른쪽 배치할때의 경우의 수를 세어 dp[a][b]에 저장 하는 식으로 코드를 짠다.
• 여기서 n일때 아예 배치하지 않는 경우의 수는 n-1일때의 모든 경우의 수와 같지만, 왼쪽에 배치하는 경우의 수와 오른쪽에 배치하는 경우의 수는 각각 오른쪽에 배치되거나 아예 없을때, 왼쪽에 배치되거나 아예 없을 때에만 배치가 가능하다.
  즉, 모든 경우의 수를 고려하면 안되고, 각 조건에 맞을때의 경우의 수만 더해야 한다.

소스코드

• 메모리 : 53148 KB
• 시간 : 216 ms

n = int(input())
dp = [[0,0,0] for i in range(n+1)]
dp[1][-1], dp[1][0], dp[1][1] = 1,1,1

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

print((dp[n][-1] + dp[n][0] + dp[n][1])%9901)