[백준] 11057번, 오르막 수 (Python)

문제

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

11057번: 오르막 수

 

코드

n = int(input())

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

for i in range(10):
    dp[1][i] = 1

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

오르막 수 문제는 맨처음 숫자로 0이 가능하고 숫자가 같아도 오르막 수 이다.

 

	0	1	2	3	4	5	6	...	9
1	1	1	1	1	1	1	1		1
2	1	2	3	4	5	6	7		10

 

n = 1일 경우에는 한자리 수 이므로

0이 맨뒤로 오는 경우의 수 0으로 => 1가지

1이 맨뒤로 오는 경우의 수 1로 => 1가지

...

9가 맨뒤로 오는 경우의 수 9로 => 1가지 

 

n = 2일 경우에는

0이 맨뒤로 오는 경우의 수 00으로 => 1가지

1이 맨뒤로 오는 경우의 수 01, 11로 => 2가지

2가 맨뒤로 오는 경우의 수 02, 12, 22로 => 3가지

...

 

이런식으로 만약 n=2 일때 5가 맨뒤에 오는 오르막수의 경우의 수를 구하고 싶으면

dp[2][5] = dp[1][0] + dp[1][1] ... dp[1][5] 까지 합한 값이 된다.