이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 점화식을 구하기 위해 그림을 그려보았다.

x축은 끝자리 수를 나타내고 y축은 n을 나타내고 있다. 그림을 통해 찾아낸 패턴은 끝자리가 k인 n자리 수의 경우의 수는 n-1자리 수의 끝자리 0~k인 수의 합이 된다.

• n=2, k=3일 경우 (n=1, k=0) + (n=1, k=1) + (n=1, k=2) + (n=1, k=3)의 값이 된다.
  -> 1+1+1+1=4
• n=3, k=2일 경우 (n=2, k=0) + (n=2, k=1) + (n=2, k=2)의 값이 된다.
  -> 1+2+3=6
• n=3, k=5일 경우 (n=2, k=0) + (n=2, k=1) + (n=2, k=2) + ... + (n=2, k=5)의 값이 된다.
  -> 1+2+3+4+5+6=21
• n=3, k=8일 경우 (n=2, k=0) + (n=2, k=1) + (n=2, k=2) + ... + (n=2, k=8)의 값이 된다.
  -> 1+2+3+4+5+6+7+8+9=45

이 패턴을 통해 각 자리수, 끝자리 별 경우의 수를 모두 메모라이제이션 할 수 있게 되었고 메모라이제이션을 할 때에 각각의 경우의 수를 저장하는 것이 아니라 그때 그때의 누적합을 저장하였다. 이렇게 하면 dp[n][9]는 n에 해당하는 출력값이 된다.

• n을 입력받는다.
• dp 배열을 (n+1)*10의 크기로 0을 채운다.
• 10번 반복하는 i에 대한 for문을 돌린다.
  -> dp[0][i]를 1로 갱신한다.
• 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  -> 10번 반복하는 j에 대한 for문을 돌린다.
  --> j+1번 반복하는 k에 대한 for문을 돌린다.
  ---> dp[i][j]에 dp[i-1][k]를 더해준다.
• dp[n][9]를 10007로 나누어 출력한다.

Code

n=int(input())
dp=[[0]*10 for _ in range(n+1)]
for i in range(10):
    dp[0][i]=1
for i in range(1, n+1):
    for j in range(10):
        for k in range(j+1):
            dp[i][j]+=dp[i-1][k]
print(dp[n][9]%10007)