[백준11057번] 오르막 수 / Python3

문제

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

예를 들어, 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

나의 풀이

이 문제는 다이나믹 프로그래밍 기법을 활용하여 이전에 구해놓은 값을 이용하면 된다. 여기서 이전에 구해놓은 값들에 해당하는 것은 맨 앞자리 수를 제외한 자릿수들에서 구한 맨 앞자리 수와 같거나 큰 수들의 경우를 모두 더하는 것이다.

가령, 세 자리의 오르막 수를 구한다고 해보자. 맨 앞자리 숫자가 0일때 가능한 것은 000, 001, 002, 003, ... , 011, 012,... 이다. 여기서 맨 앞의 0을 제외하고 생각해보면 00, 01, 02, 03, ... , 89, 99의 값이 올 수 있다. 잘보면 앞자리가 0부터인 두 자리 오르막 수들이 올 수 있다는 것을 알 수 있다. 또 맨 앞에 3이 오는 경우를 보면 앞자리 3을 제외하고는 33, 34, 35, ... , 89, 99가 올 수 있다. 이것은 앞자리가 3과 같거나 큰 수로 시작하는 오르막 수들이다.

따라서 자릿수를 i, 맨 앞자리 수를 j로 놓고 이 성질을 점화식으로 쓰면 다음과 같다.

dp[i][j] = sum(dp[i-1][j] ~ dp[i-1][9])

맨 앞자리가 1인 경우를 모두 1개씩으로 초기화를 해주고 for문을 통해 dp배열을 완성하고, 원하는 자릿수의 행을 모두 더해주면 정답이 된다. 그리고 문제에서는 수가 커질 수 있기때문에 10007로 나눈 나머지를 구하라고했으니 각 dp를 구해줄때마다와 마지막 행을 모두 더할때 10007로 모듈라 연산을 해주면된다.

코드

# 11057 오르막 수

# main
n = int(input())

dp = [[0 for _ in range(10)] for _ in range(n+1)]

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

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