[백준] 동물원

출처:: www.acmicpc.net/problem/1309

분류::

 

1. 문제 이해 및 해결과정

- 사자를 배치하는 경우는  1) 배치 안하는 경우 2) 왼쪽에 배치하는 경우 3) 오른쪽에 배치하는 경우가 있다.  ex) n=1 이라면 1번,2번, 3번경우를 모두 합해서 3가지 경우  - n-1 줄에서 사자가 배치가 안되어 있다면, 1,2,3번 경우가 가능하다 - n-1 줄에서 사자가 왼쪽에 배치되어 있다면, 1번 3번 경우가 가능하다. - n-1 줄에서 사자가 오른쪽에 배치되어 있다면, 1번 2번 경우가 가능하다. dp[i][j]=i는 우리의 크기 j=0 미배치 j=1 왼쪽배치 j=2 오른쪽 배치를 의미한다 dp[i][0]=dp[i-1][0]+dp[i-1][1]+dp[i-1][2] dp[i][1]=dp[i-1][0]+dp[i-1][2] dp[i][2]=dp[i-1][0]+dp[i-1][1]

 

2. 풀이방법

 1. [python] dp

#동물원
#https://www.acmicpc.net/problem/1309
import sys
sys.stdin = open("input.txt","r")
n=int(input())
dp=[[0]*3 for _ in range(n+1)]
dp[1][0],dp[1][1],dp[1][2]=1,1,1
mod=9901
for i in range(2,n+1):
    dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2])%mod
    dp[i][1] = (dp[i - 1][0] + dp[i - 1][2])%mod
    dp[i][2] = (dp[i - 1][0] + dp[i - 1][1])%mod
print(sum(dp[n])%mod)

 

3. 오답원인

 

4. 알게된 점