이번 문제는 다이나믹 프로그래밍을 통해 해결하였다. 전에 자릿수로 만들 수 있는 수를 만드는 문제를 풀어본 기억이 나서 점화식을 쉽게 구할 수 있었다. 점화식을 구하기 위해 도식화 해보았다.

전에 구했던 점화식과 조금 다른 점화식을 도출할 수 있었다. 전에 구했던 점화식은 dp[i][j]를 구하기 위해 dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j]를 사용했었다. 이번에는 더 간단한 패턴을 발견하였다. 이 점화식의 응용이기도 하다. dp[i][j-1]는 dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1]의 값이 될 것이다. 그러므로 dp[i][j]는 dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j] = dp[i][j-1]+dp[i-1][j]가 된다.
점화식

dp[i][j] = dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1]+dp[i-1][j]
	 = (dp[i-1][0]+dp[i-1][1]+...+dp[i-1][j-1])+dp[i-1][j]
	 = dp[i][j-1]+dp[i-1][j]

이렇게 dp리스트에 메모라이제이션을 진행해주고, dp[n]의 전체 값의 합을 구하면 결과값이 된다. 처음에 작성하였을 때에는 dp[n]의 값이 dp[n+1][9]의 값과 같아서 n보다 1번 더 dp리스트를 채우고 구하는 방식으로 구현했었다. 그러나 sum()함수로 sum(dp[n])을 구하는 것이 더 깔끔할 것 같다는 생각이 들어서 코드를 수정하였다.

• t를 입력받는다.
• t번 반복하는 for문을 돌린다.
  -> n을 입력받는다.
  -> dp 리스트를 (n+1)*10의 크기에 0을 채워 선언한다.
  -> dp[0][0]을 1로 갱신한다.
  -> 1부터 n까지 반복하는 i에 대한 for문을 돌린다.
  --> 10번 반복하는 j에 대한 for문을 돌린다.
  ---> dp[i][j]를 dp[i-1][j]+dp[i][j-1]의 값으로 갱신한다.
• dp[n]의 총 합을 출력한다.

Code

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