[백준] 11057번 : 오르막 수

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

11057번: 오르막 수

해당 문제의 아이디어는 가장 끝에있는 수에따라서 오르막의 경우의 수가 정해진다는 것입니다.

 

N= 1 일때

0일때 1개

1일때 1개

2일때 1개

3일때 1개

4일때 1개

5일때 1개

6일때 1개

7일때 1개

8일때 1개

9일때 1개

총합 : 10개

N=2 일때

0일때 10개 (00, 01,02,03,04,05,06,07,08,09)

1일때 9개 (11,12,13,14,15,16,17,18 ,19)

2일때 8개 (22, 23, 24, 25, 26, 27, 28, 29)

...

9일때 1개 (99)

N = 3 일때

0일때 (000,001 ,002, 003, 004,..., 009, 011, 012,...019, 022, 023...029, ... 099)

 

여기서 규칙을 찾을 수 있습니다. dp 테이블을 0 ~ 9 까지 담을 수 있는 테이블을 생성하고

dp[0] = dp[0] + ... + dp[9]

dp[1] = dp[1] + ... + dp[9]

N=2일때

dp[0]은 0으로 시작하는 숫자의 경우의 수의 개수

dp[1]은 1으로 시작하는 숫자의 경우의 수의 개수

...

N=3 일때

dp[0]은 N=2 일때의 dp[0] + ...  + dp[9]로 나타낼 수 있다. dp[0]은 0으로 시작하기에 0부터 9까지 이전에 있던 값으로 이어 붙힐 수 있다.

따라서 점화식은 dp[n] = dp[n] +... dp[0] 이다.

N = int(input())

dp = [1 for _ in range(10)]

for _ in range(N-1):
    for i in range(len(dp)):
        for j in range(i+1, len(dp)):
            dp[i] += dp[j]

print(sum(dp) % 10007)