백준: 15993 1, 2, 3 더하기 8

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

 

문제

15993번: 1, 2, 3 더하기 8

 

문제 풀이

 앞의 문제들과는 다르게, 홀수인 경우와 짝수인 경우에 구할 수 있는 경우의 수를 나눠서 출력하여야 한다. 따라서 DP를 구성할 때, `DP[홀수/짝수][N]`과 같이 선언하여서 각 경우에 대해 점화식을 통해 찾아가면 된다.

 

• N이 1 인 경우
  • 짝수로 나타낼 수 있는 경우 : X
  • 홀수로 나타낼 수 있는 경우 : `1`
• N이 2인 경우
  • 짝수로 나타낼 수 있는 경우 : `1 + 1`
  • 홀수로 나타낼 수 있는 경우 : `2`
• N이 3인 경우
  • 짝수로 나타낼 수 있는 경우 : `1 + 2`, `2 + 1`
  • 홀수로 나타낼 수 있는 경우 : `3`, `1 + 1 + 1`

 이와 같은 경우의 수를 나열해보면 점화식 `DP[홀수][N] = DP[짝수][N - 1] + DP[짝수][N - 2] + DP[짝수][N - 3]`과 `DP[짝수][N] = DP[홀수][N - 1] + DP[홀수][N - 2] + DP[홀수][N - 3]`를 이끌어낼 수 있다.

 

코드

from sys import stdin


if __name__ == '__main__':
    MAX, ODD, EVEN = 100001, 0, 1
    divisor = 1000000009
    dp = [[0] * 100001 for _ in range(2)]

    dp[ODD][1] = 1
    dp[ODD][2], dp[EVEN][2] = 1, 1
    dp[ODD][3], dp[EVEN][3] = 2, 2

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

    t = int(stdin.readline())

    for _ in range(t):
        n = int(stdin.readline())
        print(dp[ODD][n], dp[EVEN][n])