[1309] 동물원 in python

 

다이나믹 프로그래밍 문제!

경우의 수를 따져서 출력해야 하는데

n=1, n=2까지 직접 경우의 수를 따져보며

규칙을 발견하며 푸는 방식

---

n=0일땐 1

사자가 하나도 배치가 되어있지 않은 경우의 수도 

하나의 경우로 친다고 했으므로.

 

 

n=1일땐 3

oo, xo, ox

총 3가지

 

---

n=2일땐 7

1) n번째 줄이 모두 비어있는 상태 (oo)

 

n=1    oo.    xo.    ox

n=2    oo     oo.    oo

 

-> 3가지

dp[n-1] * 1 

: n번째 줄에는 oo 하나의 경우만 존재하고 있으므로 1를 곱하는 것

 

2) n-1번째 줄이 모두 비어있는 경우 (oo)

 

n=1   oo.  oo

n=2    xo   ox 

 

-> 2가지

dp[n-2] * 2

 

 

3) n-1, n번째 줄이 모두 채워져 있는 경우 (ox , xo)

dp[n-1]-dp[n-2]

 

 

n=int(input())
dp=[1 for _ in range(n+1)]
dp[1]=3

if n==1:
    print(dp[1])
else:
    for i in range(2,n+1):
        #1. i번째 줄에 빈 우리만 있는 경우의 수 : dp[i-1] * 1
        #2. i-1번째 줄에 빈 우리만 있는 경우의 수 : dp[i-2] * 2
        #3. i번째, i-1번째 줄에 모두 배치가 되는 경우의 수 : dp[i-1]-dp[i-2]
        # dp[i-1]-dp[i-2]
        # -> oo xo ox 중에 oo를 뺀 값
        dp[i]=2*dp[i-1]+dp[i-2]
        dp[i]%=9901
    print(dp[n])