[Baekjoon] DP - 1309 동물원

문제

1309번: 동물원

 

풀이

d[n][m]: 우리의 크기가 n일 때, m의 배치에 따라 사자를 배치를 경우의 수

1번째 경우	사자를 1번째 칸에 배치하는 경우
2번째 경우	사자를 2번째 칸에 배치하는 경우
3번째 경우	사자를 아예 배치하지 않는 경우

 

따라서, d[n][m]은 다음 사진과 같은 상황으로 배치할 수 있다.

1번째 경우

사자를 1번째 칸에 위치해있으므로, 직전에 배치할 때는 2번째 칸에 배치하거나 아예 배치하지 않을 수 있다.

 

2번째 경우

사자를 2번째 칸에 위치해있으므로, 직전에 배치할 때는 1번째 칸에 배치하거나 아예 배치하지 않을 수 있다.

 

3번째 경우

현재 사자를 배치하지 않았으므로, 직전에는 어느 경우로 배치하든 상관없다.

 

n = int(input())
# 1번째에 배치하는 경우, 2번째에 배치하는 경우, 아예 배치하지 않는 경우
d = [[0, 0, 0] for _ in range(n + 1)]
MOD = 9901


def solution(d, n):
    d[1][0] = d[1][1] = d[1][2] = 1

    for i in range(2, n + 1):
        d[i][0] = (d[i - 1][1] + d[i - 1][2]) % MOD
        d[i][1] = (d[i - 1][0] + d[i - 1][2]) % MOD
        d[i][2] = (d[i - 1][0] + d[i - 1][1] + d[i - 1][2]) % MOD
    

    return sum(d[n]) % MOD


print(solution(d, n))

 

채점 결과