[🥈1 / 백준 11057 / 파이썬] 오르막 수

 

11057번: 오르막 수

 

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

 

예제 입력 1  1	예제 출력 1  10
예제 입력 2  2	예제 출력 2  55
예제 입력 3  3	예제 출력 3  220

 

풀이

 

오르막 수를 만드는 법은 다음과 같다.

 

오르막 수의 마지막 숫자를 a 로 두고 만들 때, 마지막 수가 a보다 크거나 같은 모든 수로 오르막 수를 만들 수 있다.

즉 2자리 수를 만들고 싶을 때, 오르막 수의 마지막 수를 5로 두고 만들고 싶다면

95,85,75,65,55 이렇게 5개를 만들 수 있다.

 

그렇다면 자리수별로 오르막 수의 개수를 어떻게 구할까?

답은 메모이제이션을 통해 오르막 수의 마지막 수를 0~9 까지 담는 배열을 생성하는 것이다.

 

맨 처음에는 [1,1,1,1,1,1,1,1,1,1] 이라는 배열이 있을 것이다.

0,1,2,3,4,5,6,7,8,9 가 있을 것이니 말이다.

그리고 각각의 자리는 왼쪽부터 마지막수가 0,1,…,9 인 오르막 수의 개수를 의미한다.

 

그렇다면 2자리 수를 만들 때에는 각 배열의 현재 인덱스 이상의 원소값들을 모조리 더해주면 된다.

따라서 2자리 수는 [10, 9, 8, 7, 6, 5, 4, 3, 2, 1],

3자리 수는 [55, 45, 36, 28, 21, 15, 10, 6, 3, 1],

4자리 수는 [220, 165, 120, 84, 56, 35, 20, 10, 4, 1] 과 같이 구성된다.

 

* 수는 0부터 시작할 수 있다는 조건이 있으므로, 00, 000 과 같은 숫자도 오르막 수이다.

n = int(input())
dp = [1 for i in range(10)]

for i in range(n-1):
    for j in range(10):
        dp[j] = sum(dp[j:])
print(sum(dp)%10007)