[Silver I] 동물원 - 1309

문제 링크

성능 요약

메모리: 52648 KB, 시간: 112 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 4월 2일 14:17:28

문제 설명

어떤 동물원에 가로로 두칸 세로로 N칸인 아래와 같은 우리가 있다.

이 동물원에는 사자들이 살고 있는데 사자들을 우리에 가둘 때, 가로로도 세로로도 붙어 있게 배치할 수는 없다. 이 동물원 조련사는 사자들의 배치 문제 때문에 골머리를 앓고 있다.

동물원 조련사의 머리가 아프지 않도록 우리가 2*N 배열에 사자를 배치하는 경우의 수가 몇 가지인지를 알아내는 프로그램을 작성해 주도록 하자. 사자를 한 마리도 배치하지 않는 경우도 하나의 경우의 수로 친다고 가정한다.

입력

첫째 줄에 우리의 크기 N(1≤N≤100,000)이 주어진다.

출력

첫째 줄에 사자를 배치하는 경우의 수를 9901로 나눈 나머지를 출력하여라.

제출답안

def count(n):
    MOD = 9901

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

    return (dp[n][0] + dp[n][1] + dp[n][2]) % MOD

n = int(input())
print(count(n))

DP를 사용하기 위해서는 점화식이 중점이다. 개인적으로는 그림을 그려보면 좀 수월한 것 같다. for문에서 MOD를 통해 계속 나머지를 구하는데, 마지막에만 구해도 답은 나온다. 그러나 코드상에서 계속해서 MOD로 나누지 않는다면 그 수가 생각보다 상당히 커지게 되어 메모리를 잡아먹고 시간이 오래걸리게 된다.

모듈러 연산의 성질 중 하나는 (a + b) % c = ((a % c) + (b % c)) % c 이다. 따라서 효율성을 위해 계속 이 연산을 수행하는 것이 좋다.