[백준 11057] 오르막 수 with Python

문제 링크

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

11057번: 오르막 수

풀이

N = int(input())
dp = [[0]*10 for _ in range(N+1)]
dp[1] = [1]*10
for i in range(2, N+1):
    for j in range(10):
        dp[i][j] += sum([dp[i-1][k] for k in range(j+1)])

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

dp[N]은 N자리 수 오르막 수들 중에서 0~9까지 각각의 숫자로 끝나는 경우의 개수를 해당 숫자의 인덱스에 저장한 배열이다.

dp[1]은 0부터 9까지 모든 숫자가 오르막 수 이므로 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]이 된다.

 

N자리 오르막 수는 N-1자리 오르막 수 뒤에 N-1의 마지막 숫자와 같거나 큰 수를 붙여서 만들 수 있다.

예를 들어, N-1자리 오르막 수가 0으로 끝나면 N자리 오르막 수는 그 뒤에 0~9까지 아무 숫자나 붙여서 만들 수 있고,

N-1자리 오르막 수가 9로 끝나면 N자리 오르막 수는 그 뒤에 숫자 9만을 붙여서 만들 수 있다.

 

반대로 N자리 오르막 수가 0으로 끝나기 위해서는 N-1자리 오르막 수가 반드시 0으로 끝나야 하고,

N자리 오르막 수가 9로 끝나기 위해서는 N-1자리 오르막 수가 0~9까지 어떤 수로 끝나도 상관이 없다.

 

따라서, dp[N]은 아래와 같이 나타낼 수 있다.

dp[N] = [
    dp[N-1][0],
    dp[N-1][0] + dp[N-1][1],
    dp[N-1][0] + dp[N-1][1] + dp[N-1][2],
  
    ...

    dp[N-1][0] + dp[N-1][1] + ... + dp[N-1][9]
]

dp[N]의 모든 원소를 다 더 하면 N자리 오르막 수의 전체 개수가 된다.