Baekjoon [11057] 오르막 수 - python

문제

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

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

문제 코드

n = int(input())
dp = [[0 for _ in range(9)]for _ in range(1000)]

        #1,2,3,4,5,6,7,8,9
dp[0] = [1,1,1,1,1,1,1,1,1] # 초기 세팅
dp[1] = [9,8,7,6,5,4,3,2,1]
if n == 1:
    print(sum(dp[n-1])+1)
elif n == 2:
    print(sum(dp[n-1]) + sum(dp[n-2])+1)
else:
    for i in range(3,n+1):
        for j in range(9):
            dp[i-1][j] = sum(dp[i-2][j:10]) % 10007
    answer = 0
    for i in range(n):
        answer += sum(dp[i])
    print((answer+1)% 10007)
# 0,1,2,3,4,5,6,7,8,9 10개
#
# 1(1~9) 9
# 2(2~9) 8
# 3(3~9) 7
# 4(4~9) 6
# 5(5~9) 5
# . 4
# . 3
# . 2
#  1
#

# 1xx -> 45개       (3자리수)
# 2xx -> 36개
# 3xx -> 28개
# 4xx -> 21개
# 5xx -> 15개
# 6xx -> 10개
# 7xx -> 6개
# 8xx -> 3개
# 9xx -> 1개

# 1xxx -> (45+36+28+21+15+10+6+3+1)

문제 접근

dp문제라서 점화식을 어떻게 구할지 생각을 해보았습니다. 초기 step으로 n이 1일때는 0

9까지의 값이므로 초기값 10을 고정합니다. 이때 0은 특별한 수이므로 모든 연산에서 마지막 셈을 더하여 계산하였습니다. 코드 내 주석처럼 이후 10부터~ 9~9사이의 숫자는 일의자리숫자나 나올 수 있는 경우의 수를 다 더하면 됩니다.
더 설명하자면 n이 3일 때 1xx기준으로 xx는 n이 2일때 나올 수 있는 경우의 수 입니다. 2xx기준은 1x로 시작하는 수를 제외한 모든 수를 다 더하면 됩니다.
따라서

dp[i-1][j] = sum(dp[i-2][j:10]) % 10007

해당 수식을 바탕으로 값을 계산하여 넣었습니다. 이때 10007로 계산을 다 한후에 넣을수도 있지만 n이 1000까지가 진행되므로 중간 값이 너무 커져서 sum이 작동하는데 메모리를 많이 잡아먹을 것이라 예상하여 값을 넣을 때 10007로 나누어 넣었습니다.