백준: 15990 1, 2, 3 더하기 5

1, 2, 3 더하기 시리즈

• 1, 2, 3 더하기
• 1, 2, 3 더하기 2
• 1, 2, 3 더하기 3
• 1, 2, 3 더하기 4
• 1, 2, 3 더하기 5
• 1, 2, 3 더하기 6
• 1, 2, 3 더하기 7
• 1, 2, 3 더하기 8
• 1, 2, 3 더하기 9

 

문제

15990번: 1, 2, 3 더하기 5

 

문제 풀이

 기존의 문제와 달리 연속된 숫자를 사용할 수 없다는 조건이 추가된 문제이다. 문제를 풀기 위해서 DP를 2차원 배열로 나누어 생각하면 쉽게 문제를 해결할 수 있다. 예를 들어 1, 2, 3 더하기의 경우 점화식을 `dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]`을 정의할 수 있었다. 하지만 이 문제에서는 뒤의 숫자가 연속되는지 확인이 필요하다.

 

 따라서 DP를 2차원 배열로 `dp[구하고자 하는 수의 합][마지막 뒷자리의 수]`와 같이 구성하고 각 요소에 대해 다음과 같이 나타낼 수 있다.

 

dp[0] = [0, 0, 0, 0]
dp[1] = [0, 1, 0, 0]
dp[2] = [0, 0, 1, 0]
dp[3] = [0, 1, 1, 1]

 즉 DP[1]의 경우 DP[1][1]을 제외하고 나머지의 경우는 1을 나타낼 수 없다. DP[2]의 경우 `1 + 1`은 연속되고 2를 사용하여서만 2를 구할 수 있다. DP[3]의 경우 뒷자리가 1, 2, 3으로 오는 경우 모두 나타낼 수 있는데 `2 + 1`, `1 + 2`, `3`과 같은 경우의 수가 있을 수 있다.

 

 이와 같은 규칙을 통해 문제를 풀기 위한 점화식을 이끌어 낼 수 있다.

• `dp[n][1] = dp[n - 1][2] + dp[n - 1][3]`
• `dp[n][2] = dp[n - 2][1] + dp[n - 2][3]`
• `dp[n][3] = dp[n - 3][1] + dp[n - 3][2]`

 

코드

from sys import stdin


if __name__ == '__main__':
    MAX = 100001
    divisor = 1000000009
    dp = [[0] * 4 for _ in range(MAX)]

    dp[0] = [0] * 4
    dp[1] = [0, 1, 0, 0]
    dp[2] = [0, 0, 1, 0]
    dp[3] = [0] + [1] * 3

    for i in range(4, MAX):
        dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % divisor
        dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % divisor
        dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % divisor

    t = int(stdin.readline())

    for _ in range(t):
        n = int(stdin.readline())
        print(sum(dp[n]) % divisor)

 각 경우의 수를 구할때마다 `divisor`로 나누어주지 않으면 메모리 초가가 발생한다.