[Python]백준 1309/동물원/dp

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

1309번: 동물원

 

⚡️ 문제 설명

 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램

⚡️ 해결 방법

#왼쪽에 있는 경우
dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901

#오른쪽에 있는 경우
dp[i][1]=(dp[i - 1][0] + dp[i - 1][2])%9901

#둘다 없는 경우
dp[i][2]=(dp[i - 1][0]+ dp[i - 1][1] + dp[i - 1][2])%9901

🟢 왼쪽에 있는 경우 = 전단계에서 오른쪽에 있는 경우 ☑️ + 그 전단계에서 둘다 없는 경우 

dp[i][0]=(dp[i-1][1]+dp[i-1][2]) % 9901

	☑️
🟢

🔵 오른쪽에 있는 경우 = 전단계에서 왼쪽에 있는 경우 ☑️ + 그 전단계에서 둘다 없는 경우

dp[i][1]=(dp[i - 1][0] + dp[i - 1][2]) % 9901

☑️
	🔵

🔴 둘다 없는 경우 = 전단계에서 왼쪽에 있는 경우 + 전단계에서 오른쪽에 있는 경우 + 전단계에서 둘다 없는 경우
dp[i][2]=(dp[i - 1][0]+ dp[i - 1][1] + dp[i - 1][2]) % 9901

 

 

dp  

	왼쪽	오른쪽	둘 다 X
dp[0]	1	1	1
dp[1]	2	2	3
dp[2]	5	5	7
dp[3]	12	12	17

결과 = sum(dp[n-1])%9901 = (12 + 12 + 17)%9901 = 41

⚡️ 코드

import sys
input = sys.stdin.readline

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

for i in range(1,n):
    #왼쪽에 있는 경우
    dp[i][0]=(dp[i-1][1]+dp[i-1][2])%9901
    #오른쪽에 있는 경우
    dp[i][1]=(dp[i - 1][0] + dp[i - 1][2])%9901
    #둘다 없는 경우
    dp[i][2]=(dp[i - 1][0]+ dp[i - 1][1] + dp[i - 1][2])%9901
    
print(sum(dp[n-1])%9901)