백준 1309 동물원

문제풀이

세 개의 요소를 활용한 dp로 문제를 풀겠습니다.

1. 배열 자료구조인 dp의 각 요소의 의미는 아래와 같습니다.

dp[n][0] : n번째 행의 왼쪽 칸에 사자가 있을 경우의 수.

dp[n][1] : n행의 오른쪽 칸에 사자가 있을 경우의 수.

dp[n][2] : n행에 사자가 없는 경우의 수.

2. 각 요소의 점화식은 다음과 같습니다.

2-1. dp[n][0] = dp[n-1][1]+dp[n-1][2] ; n행의 왼쪽에 사자를 넣기 위해서는 윗행의 오른쪽에 사자가 있거나(dp[n-1][1]) 윗행에 사자가 아예 없어야(dp[n-1][2]) 합니다.

2-2. dp[n][1] = dp[n-1][0]+dp[n-1][2] ; n행의 오른쪽에 사자를 넣기 위해서는 윗행의 왼쪽에 사자가 있거나 윗행에 사자가 아예 없어야 합니다.

2-3. dp[n][2] = dp[n-1][0]+dp[n-1][1]+dp[n-1][2] ; n행에 사자를 넣기 않으려면, 윗행에 사자가 어디에 있든 아예 없든 상관 없습니다.

3. dp의 요소가 너무 커지지 않도록 %9901을 해주며, n=1부터 입력받는 N까지 진행해준 후, sum(dp[n])%9901을 반환합니다.

 

Python Code

def main(n):
    dp = [1,1,1]
    for _ in range(n-1):
        tmp = [(dp[1]+dp[2])%9901, (dp[0]+dp[2]%9901), (dp[0]+dp[1]+dp[2])%9901]
        dp = tmp
    print(sum(dp)%9901)
    
if __name__ == '__main__':
    main(int(input()))

문제링크

1309번: 동물원