BOJ-11057 오르막 수

https://www.acmicpc.net/problem/11057

문제 소개

수의 자리가 오름차순을 이루는 수를 오르막 수라고 한다.

수의 길이 n이 주어졌을 때, 오르막 수의 개수를 구한다.

문제 풀이

dp로 풀이하였다.

리스트 dp는 2차원 리스트로, dp[x][y]는 x + 1자리 오르막 수 중 y로 끝나는 수의 개수를 의미한다.

예를 들어, dp[2][3]은 3자리 오르막 수 중 3으로 끝나는 수의 개수이다.

수의 자리는 오름차순을 이루어야 하므로 y로 끝나는 수의 끝에 붙을 수 있는 숫자는 y보다 같거나 커야 한다.

이를 식으로 나타내면 아래와 같다.

dp[x + 1][y] = sum(dp[x][0:y + 1])

작성한 코드에서는 위 식을 반복하여 리스트 dp를 완성하도록 하였다.

코드

# dp[x][y]는 x + 1자리 오르막 수 중 y로 끝나는 수의 개수
n = int(input())
dp = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

for _ in range(n - 1):
    t = []
    for i in range(10):
        t.append(sum(dp[-1][0:i + 1]))
    dp.append(t)

print(sum(dp[-1]) % 10007)