BOJ [Silver I] 오르막 수 - 11057

문제 링크

분류

다이나믹 프로그래밍(dp)

문제 설명

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

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

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

입력

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

출력

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

입출력 예

입력	출력
1	10
2	55
3	220

아이디어

• 10844번 계단 수랑 같은 방식으로 풀면 됨

• 이번에는 시작이 0인 수도 가능하기 때문에 예외처리 해줄 것도 없음!

• 그림처럼 dp[i][j]는 dp[i-1]에서 0~j열의 합

내 코드

n = int(input())
dp = [[1] * 10 for _ in range(n+1)]  # [자릿수][끝에 오는 수]

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

print(sum(dp[n])%10007)

다른 사람 코드

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

for i in range(1, n):
    for j in range(1, 10):
        dp[j] += dp[j-1]

• 어차피 n번째 행에 대해서만 볼 거니까 1차원으로 만들고 행 바뀔 때마다 열 값 바꿔주도 됨