백준: 15992 1, 2, 3 더하기 7

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

 

문제

15992번: 1, 2, 3 더하기 7

 

문제 풀이

N이라는 수를 1, 2, 3이라는 숫자를 사용하여 구할 때, M개의 숫자를 사용하여서 구할 수 있는 경우의 수를 찾는 문제이다. 문제를 풀기 위해서는 구하고자 하는 수 N과 사용하여야 하는 숫자 M이 있으므로 2차원 배열인 `dp[구하고자 하는 수][사용한 수]`를 메모이제이션 하면서 구할 수 있다.

 

• N이 1인 경우
  
  • 1만 사용하여 나타낼 수 있다.
• N이 2인 경우
  • 하나 사용하는 경우: 2
  • 두개 사용하는 경우: 1 + 1
• N이 3인 경우
  • 하나 사용하는 경우: 3
  • 두 개 사용하는 경우: 1 + 2, 2 + 1
  • 세 개 사용하는 경우: 1 + 1 + 1

 즉, 각 숫자마다 몇 개의 수로 나타낼 수 있는지 메모이제이션하면 된다. 따라서 점화식 `dp[N][M] = dp[N - 1][M - 1] + dp[N - 2][M - 1] + dp[N - 3][M - 1]`을 이끌어 낼 수 있다. 

 

코드

from sys import stdin


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

    # 1을 나타낼 수 있는 경우
    dp[1][1] = 1
    # 2를 나타낼 수 잇는 겨우
    dp[2][1] = 1
    dp[2][2] = 1
    # 3을 나타낼 수 있는 경우
    dp[3][1] = 1
    dp[3][2] = 2
    dp[3][3] = 1

    for i in range(4, MAX):
        # 사용할 수 있는 수는 현재수의 크기 만큼이다.
        # 예를 들어 5의 경우 숫자 6개로 사용하여 만들 수 있는 경우는 없다.
        for j in range(1, i + 1):
            dp[i][j] = (dp[i - 1][j - 1] + dp[i - 2][j - 1] + dp[i - 3][j - 1]) % divisor

    t = int(stdin.readline())

    for _ in range(t):
        n, m = map(int, stdin.readline().split())
        print(dp[n][m])