(파이썬 python) 백준 11057번 : 오르막 수

# 11507 번 : 오르막 수

n = int(input())

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

dp[1] = [1] * 10

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

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

 

dp문제는 점화식을 구하는 것이 가장 중요하다. 그리고 점화식을 구하려면 손으로 써가면서 규칙을 찾는 방법이 제일 좋은 것 같다

 

n = 1일때

0,1,2,3,4,5,6,7,8,9 로 총 10개의 오르막 수 가 있다.

 

n = 2일때

00~09 :10개

11~19 : 9개

22~29 : 8개

...

99 : 1개

로 10+9+8+7+6+5+4+3+2+1 = 55개의 오르막 수가 있다.

 

n = 3일때 (이때부터는 0으로 시작하면 숫자가 너무 많아서 9로 시작하는 숫자부터 생각해보았다)

999 : 1개

888,889,899 : 3개

777,778,779,788,789,799 : 6개 

666,667,668,669,677,678,679,688,689,699 : 10개

 

여기까지 쓰면서 규칙을 찾을 수 있었다. 9로 시작하는 수부터 생각했을 때 9xx 는 dp[2][9] , 8xx는 dp[2][9]+dp[2][8], 7xx는 dp[2][7]+dp[2][8]+dp[2][9], 6xx는 dp[2][6]+dp[2][7]+dp[2][8]+dp[2][9] 이런식으로 구하면 된다.

 

읽어주셔서 감사합니다!