BOJ :: 오르막 수 (no.11057)

문제

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

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

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

입력

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

출력

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

🤔 생각

• 왠지 메모이제이션을 어떻게 할지가 영 어려웠던 문제다...
• 아래 블로그 풀이를 참고하여 풀었다.

참고링크
https://suri78.tistory.com/92

메모이제이션

dp[n][i] : n 자릿수의 가장 오른쪽 값이 i일 때 가능한 수열의 갯수

케이스

마지막 수가 N이면, 1~N-1 모두 이전 수로 올 수 있다. (오름차순이라면)
dp[n][i] = ∑ dp[n-1][j] (j=0 ... i)
이 식이 성립한다.

🔥 점화식
dp[i] = dp[i] + dp[i-1]
1로 만든 수열은 2를 포함한 조합에도 종속된다는 원리다.

📌 내 풀이

import sys
input = sys.stdin.readline

N = int(input())
dp = [1]*10

for _ in range(N-1):
    for i in range(1,10):
        dp[i] = (dp[i] + dp[i-1]) % 10007

print(sum(dp) % 10007)

✔ 회고

• N-1로 일정 숫자 범위가 올 때는, 각 수만큼의 최댓값을 메모이제이션 한다고 생각하자