[DP] 백준 11057. 오르막수

10844 쉬운 계단 문제를 풀면 dp 배열을 2차열로 활용하는 게 나온다. 이 원리를 그대로 적용할 수 있겠다 싶었다. 자리수에 대한 관계를 점화식으로 표현할 수 있다는 게 공통점이었기 때문이다. 

import sys
input = sys.stdin.readline
l = int(input())

d = [[0]*10 for _ in range(l+1)]
for k in range(10):
    d[1][k] = 1
for i in range(2,l+1):
    for j in range(10):
        d[i][j] = sum(d[i-1][j:])

print(sum(d[l])%10007)

sum을 두 번 쓰는 게 낯설었는데, 나열해보면 그 이유를 알 수 있었다.

 

 

# d[2][0]
# d[2][4] = d[1][4::-1]
# d[2][2] = 22 23 24 25 26 ... 29
# d[3][2] = 222 223 224 225 226 ... 229 + 233

혹시나 해서 다른 분 sol을 찾아봤는데, 나보다 간결하게 풀어서 다음에 다시 읽어봐야겠다.!

 

 

* 참고

태윤개발블로그