https://www.acmicpc.net/problem/11057
문제
오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.
예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.
수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.
입력
첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.
출력
첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.
코드
N = int(input())
dp = [[0 for i in range(10)]for j in range(1001)]
dp[1] = [1,1,1,1,1,1,1,1,1,1]
for i in range(2,N+1):
for j in range(10):
dp[i][j] = sum(dp[i-1][0:j+1])
print(sum(dp[N]) % 10007)풀이
i = 자릿수
j = 맨 뒤에 오는 수
이고 각 dp[i][j]에는 가능한 경우의 수를 지정해주었습니다.
N이 1~3까지인 경우까지만 살펴봅시다.
| 자릿수 | 맨 뒷자리 수(0~9)에 따른 경우의 수 | 총 오르막 수 |
|---|---|---|
| 1 | 1 1 1 1 1 1 1 1 1 1 | 10 |
| 2 | 1 2 3 4 5 6 7 8 9 10 | 55 |
| 3 | 1 3 6 10 15 21 28 36 45 55 | 220 |
위의 규칙을 살펴보면, 자리수가 1일때 각 숫자들이 맨뒷자리에 올 수 있는 개수는 1씩입니다. 왜냐하면 자릿수가 1이기 때문에.
자릿수가 2일때를 살펴보면 첫째항이 1이고 1씩 증가하는
등차수열임을 알 수 있습니다. 왜냐하면 두 자릿수의 경우 맨 뒤에 오는 수보다 작거나 같은 수 하나만 앞에 올 수 있기 때문에 뒷자리 수가 n이면 0~n까지 n+1개의 경우가 가능합니다.
이렇게 세 자리수까지 구해보면 위와같은 표가 나올 수 있는데 규칙을 찾아보면
해당 위치의 윗 열의 처음부터 해당 위치 바로 위까지 숫자의 합이라는 걸 알 수 있습니다.
ex) 세 자리수이고 맨 뒤에 3이 오는 경우의 수는 두 자리수면서 뒤에 오는 수가 0~3까지인 경우의 합 = 1+2+3+4 = 10
고로
dp[i][j] = sum(dp[i-1][0:j+1]) 로 점화식을 세워 해결하였습니다.
