백준 파이썬 1309번 동물원

🚀접근하기

<다이나믹 프로그래밍>

어려웠다.. 경우의 수를 나눠보려고 했는데 잘 나누지 못했다..

결국 1.N번째 줄에 사자가 없는 경우 (X X) 2.N번째 줄 왼쪽에 사자가 있는 경우(O X) 3.N번째 줄 오른쪽에 사자가 있는 경우(X O) 이렇게 3가지의 경우의 수로 나누어 풀면 되는 문제였다.

🎉코드

N=int(input())

dp=[]
for i in range(0, N+1):
    dp.append([0,0,0])

dp[1][0]=1
dp[1][1]=1
dp[1][2]=1

for i in range(2, N+1):
    dp[i][0]=(dp[i-1][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])%9901

print(sum(dp[N])%9901)

1.N번째 줄에 사자가 없는 경우 (X X)엔 윗줄에서 X O, O X, X X의 경우가 가능하다.

2.N번째 줄 왼쪽에 사자가 있는 경우(O X)엔 윗줄에서 X O, X X의 경우가 가능하다.

3.N번째 줄 오른쪽에 사자가 있는 경우(X O)엔 윗줄에서 O X, X X의 경우가 가능하다.

💪다짐

#case를 잘 나누는게 진짜 중요하구나를 느낌..
#근데 일단 다 구하고 점화식 되는지 보는 것도 좋을듯

#1.점화식 간단하게 구해지는지 확인
#2.경우의 수 나누기 (보통 dp는 이차원 배열 쓰면 해결되는 듯)
#3.경우의 수는 여러가지 방법으로 나눌 수 있다