[백준 16195번] 파이썬 - 1,2,3 만들기 9

백준 16195 1,2,3 더하기 9

시간 제한 1초, 메모리 제한 512MB

# 조건

• 정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다.
• 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1
• 정수 n과 m이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
  • 단, 사용한 수의 개수는 m개 이하 이어야 한다.

입력

• 첫째 줄에 테스트 케이스의 개수 T가 주어진다.
• 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n과 m이 주어진다.
• n은 양수이며 1,000보다 작거나 같다. m도 양수이며, n보다 작거나 같다.

출력

• 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.
  • 단, 사용한 수의 개수는 m개 이하 이어야 한다.

# 접근 방법

• 이전에 계산된 값을 활용해야 하므로 dp를 이용해준다.
• dp[i][j] 에서 i는 만들 숫자, m은 사용된 숫자의 개수이다.
• 1,2,3을 만드는 방법을 미리 계산해준다.
  • dp[1][1] = 1
  • dp[2][1], dp[2][2] = 1, 1
  • dp[3][1], dp[3][2], dp[3][3] = 1, 2, 1
• 4를 만드는 방법은 문제에서와 같이 7개이다.
  • 1+1+1+1
  • 1+1+2
  • 1+2+1
  • 2+1+1
  • 2+2
  • 1+3
  • 3+1
  • dp[4][1], dp[4][2], dp[4][3], dp[4][4] = 0, 3, 3, 1
• 위의 규칙을 살펴보면
  • 1개로 만드는 경우는 0
  • 2개로 만드는 경우는 1을 1개로 만든 것에서 3을 더하는 것, 2를 1개로 만드는 것에서 2를 더하는 것, 3을 1개로 만드는 것에서 1을 더하는 것이다.
• 즉, dp[i][j] = dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1]이 되는 것을 알 수 있다.

import sys
input = sys.stdin.readline

T = int(input())
dp = [[0] * 1001 for _ in range(1001)]
dp[1][1] = 1
dp[2][1], dp[2][2] = 1, 1
dp[3][1], dp[3][2], dp[3][3] = 1, 2, 1
for i in range(4, 1001):
    for j in range(1, 1001):
        dp[i][j] = (dp[i-1][j-1] + dp[i-2][j-1] + dp[i-3][j-1]) % 1000000009
for _ in range(T):
    a, b = map(int, input().split())
    print(sum(dp[a][:b+1]) % 1000000009)