[백준] Q1309 동물원 (python , 다이나믹 프로그래밍)

 

백준 동물원 문제를 다이나믹 프로그래밍으로 풀어보았다.

case0,1,2 는 각각 사자가 없을때, 왼쪽에 있을때, 오른쪽에 있을 때를 의미한다.

 

def main():
    N = int(input())
    case =[1,1,1]
 
    for i in range(2,N+1):
        c0 = case[0] + case[1] + case[2]
        c1 = case[0] + case[1]
        c2 = case[0] + case[2]
        case[0] = c0%9901
        case[1] = c1%9901
        case[2] = c2%9901
 
    print(sum(case)%9901)
 
 
if __name__ == "__main__":
    main()