🍋 문제링크

https://www.acmicpc.net/problem/11057

11057번: 오르막 수

🍎 코드 제출 기록 (메모리 및 시간)

메모리 : 123172 KB

시간 : 120 ms

🍉 Code

N = int(input())
dp = [[0 for _  in range(19)] for _ in range(1009)]

dp[1] = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

for i in range(2, N+1):
    for j in range(10):
        if j == 0:
            dp[i][j] = sum(dp[i-1])
        else:
            dp[i][j] = dp[i][j-1] - dp[i-1][j-1]

print(sum(dp[N])%10007)

🥝 메모

DP[][] 배열을 2차원으로 선언

DP[x][y] → x : 입력으로 주어지는 숫자 ( = 오르막수의 길이 )

          y : 가장 큰 자리의 숫자

< 예시 >
000    → dp[3][0]
3367 → dp[4][3]

dp[1] 는 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1] 으로 초기화

위의 그림에 의해, dp[k][0] = dp[k-1][0] + dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]

                 dp[k][1] =                       dp[k-1][1] + dp[k-1][2] + ... + dp[k-1][9]   

                 dp[k][2] =                                            dp[k-1][2] + ... + dp[k-1][9]      

                  .

                  .

                  .

            dp[k][9] =                                                               ...      dp[k-1][9]

라는 규칙을 찾을 수 있으므로