카테고리 없음

DP) 1309.동물원

Carnival7 2022. 2. 12. 23:05

문제 : 1309. 동물원

 

1309번: 동물원

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

www.acmicpc.net

규칙

  1. 가로로 두 칸, 세로로 N칸인 동물원이 있다.
  2. 사자를 가로, 세로로 붙어 있게 배치하면 안된다.

목표

동물원에 사자를 배치하는 가능한 모든 경우의 수는?

Solution

  1. d[n][m] : 세로로 n칸인 우리에 배치할 때, n번째 줄은 m번 방법으로 배치하는 경우의 수
  2. m : 3개의 방법 중 하나.
    1) d[n][0] : n번 줄에 배치하지 않음
    2) d[n][1] : n번 줄의 왼쪽에 배치함
    3) d[n][2] : n번 줄의 오른쪽에 배치함
  3. 점화식
    1) d[n][0] = d[n-1][0] + d[n-1][1] + d[n-1][2]
    2) d[n][1] = d[n-1][0] + d[n-1][2]
    3) d[n][2] = d[n-1][0] + d[n-1][1]
  4. 답은 sum(d[n])

소스 코드

n=int(input())  
mod = 9901  

d=[[0] * 3 for _ in range(n+1)]  

d[1][0] = 1  
d[1][1] = 1  
d[1][2] = 1  

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

print(sum(d[n])%mod)