숫자 만들기

문제

숫자 1, 2, 3을 이용하여 숫자 N을 만드는 경우의 수를 출력하는 프로그램을 작성하시오. 예를 들어, N이 4일 경우에는 다음의 7가지 경우가 존재한다. 단, 경우의 수가 매우 많을 수 있으므로, 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.

1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1

 

입력

첫 번째 줄에 N이 주어진다. ( 1 ≤ N ≤ 100,000 )  

출력

1, 2, 3을 이용하여 N을 만들 수 있는 경우의 수를 1,000,007 로 나눈 나머지를 출력한다.  

예제 입력
4
예제 출력
7

예제 입력
200
예제 출력
290816

#코드

import sys
input=sys.stdin.readline
 
def dpMakeNum(n):
    if(n>3):dptable=[0]*(1+n)
    else:dptable=[0]*(1+3)
    dptable[1]=1
    dptable[2]=2
    dptable[3]=4
    # an = a_n-1 + a_n-2 + a_n-3
    for i in range(4,n+1):
        dptable[i]=(dptable[i-1]+dptable[i-2]+dptable[i-3])%1000007
    return dptable[n]
 
    
if __name__=="__main__":
    n = int(input().strip())
    print(dpMakeNum(n))

 

# 1, 2, 3의 값이 고정이 아닌 m이라고 가정하였을 경우의 코드

import sys
 
# 1. Table을 어떻게 정의했는지
# 2. 점화식을 어떻게 세웠는지
# T(i) = 1 ~ M 까지의 숫자를 이용해서 숫자 i를 만드는 경우의 수
# T(i) = T(i-1) + T(i-2) + ... + T(i-M)
 
if __name__ == "__main__":
  n, m = map(int, sys.stdin.readline().split())
  table = [0 for _ in range(100000)]
  
  # 1 ~ m
  table[1] = 1
  sum = 0
  for i in range(2, m+1): 
    sum += table[i-1]
    table[i] = sum + 1
    
  # n, m = 5, 3  
  # t[2] = 2, t[3] = 3, 
  # 4 ~ 6
  # i = 4 -> 1, 2
  for i in range(m+1, n+1  ):
    for j in range(i-m, i):
      table[i] += table[j]
      
  print(table[n])

예제 입력
4 3
예제 출력
7