[백준] 1309 동물원

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

1309번: 동물원

n > 1일 때 

사자를 0마리 넣을 때, 1마리 넣을 때, 2마리 넣을 때,, n마리 넣을때 까지 하여 경우의 수를 구하였다. 

 

n = 0 >>  1가지로 취급  [0,0,0]로 0번째 행 설정

n = 1 >>  3 = 1 + 2  [1,1,1]로 1번째 행 설정

n = 2 >>  7 = 1 + 4 +2

n = 3 >> 17 = 1 + 6 + 8 + 2

n = 4 >> 41 = 1 + 8 + 18 + 12 + 2

n = 5 >>101 = 1 + 10 + 32 + 38 + 16 + 2

 

사자를 우리에 넣을 때

n-1번째 행에서 0마리를 넣은 경우 >> n번째 행에서 0마리를넣는 경우, 왼쪽 열에 1마리 넣는 경우, 오른쪽 열에 1마리 넣는 경우 

n-1번째 행에서 왼쪽에 1마리를 넣은 경우 >> n번째 행에서 0마리를넣는 경우, 오른쪽 열에 1마리 넣는 경우 

n-1번째 행에서 오른쪽에 1마리를 넣은 경우 >> n번째 행에서 0마리를넣는 경우, 왼쪽 열에 1마리 넣는 경우 

로 나누어 규칙을 찾았다.

마지막에 9901로 나머지를 나누고 나머지를 출력하니 런타임 오류가 나, 각 경우마다 9901로 나누어주었다.

n = int(input())

  # n = 0일 때에도 사자를 넣는 방법으로 간주
 # 0번째줄을 제외하고 n만큼 행을 만듦
cage =[ [0,0,0]  for _ in range(n+1) ]


cage[1][0] = 1
cage[1][1] = 1
cage[1][2] = 1


for i in range(2,n+1):
    cage[i][0] = (cage[i-1][0] + cage[i-1][1] + cage[i-1][2])  % 9901  # n-1번째 행에 사자를 넣지 않을 때
    cage[i][1] =(cage[i-1][0] + cage[i-1][2]) % 9901  # n-1번째 행에 사자를 넣지 않거나 사자를 오른쪽에 넣을 때
    cage[i][2] = (cage[i-1][0] + cage[i-1][1]) % 9901  # n-1번째 행에 사자를 넣지 않거나 사자를 왼쪽에 넣을 때

print(sum(cage[n]) % 9901)