[Python] boj no. 11507 : 오르막 수

Problem

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

Idea

오르막 수는 수의 자리가 오름차순을 이루는 수이다. 오르막 수가 되기 위해서는 임의의 자리의 수에 대해 높은 자리의 수가 그 수보다 작거나 같아야만 한다.

행의 길이가 10인 dp 배열을 선언하고 각 배열이 인덱스를 끝자리 수로 가지는 오르막 수의 개수라고 가정하자. 끝자리가 i인 오르막 수는 가장 오른쪽 자리가 0~i인 오르막 수의 가장 오른쪽에 i를 추가하는 것으로 얻을 수 있다. 즉, dp[n][i] = sum(dp[n-1][0:i])이 된다.

dp 배열을 1로 초기화하고 위의 과정을 n번 반복하면 오른쪽 자리의 수가 0부터 9인 길이가 n인 오르막 수의 갯수를 구할 수 있다.

Code

N = int(input())

dp = [[1 for _ in range(10)] for _ in range(2)]
cur = 0
for _ in range(1, N):
    next = (cur+1)%2
    
    for i, value in enumerate(dp[cur]):
        dp[next][i] = sum(dp[cur][:i+1]) % 10007
    
    cur = next
  
print(sum(dp[cur])%10007)

Comment