문제 : 1309. 동물원
1309번: 동물원
첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.
www.acmicpc.net
규칙
- 가로로 두 칸, 세로로 N칸인 동물원이 있다.
- 사자를 가로, 세로로 붙어 있게 배치하면 안된다.
목표
동물원에 사자를 배치하는 가능한 모든 경우의 수는?
Solution
- d[n][m] : 세로로 n칸인 우리에 배치할 때, n번째 줄은 m번 방법으로 배치하는 경우의 수
- m : 3개의 방법 중 하나.
1) d[n][0] : n번 줄에 배치하지 않음
2) d[n][1] : n번 줄의 왼쪽에 배치함
3) d[n][2] : n번 줄의 오른쪽에 배치함 - 점화식
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] - 답은 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)