[백준] 1309 동물원 파이썬 python

문제링크

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

1309번: 동물원

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
 
d = [[0]*3 for _ in range(n+1)]
d[1] = [1,1,1]
for i in range(2,n+1):
    for j in range(3):
        if j ==0:
            d[i][j] = sum(d[i-1])%9901
        elif j==1:
            d[i][j] = (d[i-1][0]+d[i-1][2])%9901
        else:
            d[i][j] = (d[i-1][0]+d[i-1][1])%9901
 
print(sum(d[n])%9901)
 

 

POINT

-DP로 접근

-풀이 방법:

'가로로도 세로로도 붙어 있게 배치할 수는 없다'라는 조건이 핵심이다.

따라서 직전 행에 사자가 배치되었는지, 그렇다면 왼쪽 혹은 오른쪽에 배치되었는지에 대한 정보를 저장해야한다. 

d[i][j] : i번째 행에 배치 없음(j=0) / 왼쪽 배치(j=1) / 오른쪽 배치(j=2) 했을 때의 경우의 수

 

d[i][0] = i번째 행에 배치하지 않을 거면 직전 행이 어떻든 아무 상관이 없음.         

        = d[i-1][0] + d[i-1][1] + d[i-1][2]

 

d[i][1] = i번째 행 왼쪽에 배치할거면 직전 행 왼쪽에 사자가 있으면 안됨.

         = d[i-1][0] + d[i-1][2]

 

d[i][2] = i번째 행 오른쪽에 배치할거면 직전 행 오른쪽에 사자가 있으면 안됨.

         = d[i-1][0] + d[i-1][1]