[백준_1309] 동물원 python

dp 구현과정

n = int(input())

dp = [0] * (n+1)

for i in range(n+1):

    dp[i] = [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 # 이번에 오른쪽을 선택하는것은 전에 선택하지않았거나, 왼쪽을 선택했을 경우 가능함

 

# cf) 9901로 나눈 나머지만 신경쓰므로 미리 계산하는것이 메모리 초과를 일으키지 않음!

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