[백준/Python] 11057 - 오르막 수

문제

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

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

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

입력

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

출력

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

풀이
난 이런 형태의 dp에 굉장히 약한 편이다
단순히 경우의 수를 나열해서는 규칙을 찾아내기가 굉장히 어려운 문제이고
dp 리스트를 이중으로 사용해야하다보니 가로축과 세로축을 어떻게 의미 부여해야할지 감을 잡기 어려워하는 편이다
이 문제와 동일한 점화식을 갖는 문제는 정말 많은 편이지만 풀 때마다 잘 모르겠다 ㅋㅋ

이 문제를 풀기 위해 중요한 점은 n의 길이에 따라 경우의 수의 개수를 구하는 것은 맞지만 수의 마지막 자리 숫자가 0-9 일때의 경우의 수를 세는 것이다

그러나 이렇게 풀면 n=1일 때의 원래 답인 10이 dp[2][9]에 위치하게 된다
따라서 초기에 dp를 초기화할 때 n이 0부터 시작하는 것처럼 초기화해준다

코드

import sys

n = int(sys.stdin.readline())

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


for i in range(1, n+1):
    dp[i][0] = 1
    for j in range(1,10):
        dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][9]%10007)