[백준11057] 오르막수

문제

---

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

11057번: 오르막 수

생각의 흐름

---

예컨대, 세 자리 수를 구할 때 끝자리가 2라면 앞의 두자리에 올 수 있는 수는 2보다 작거나 같은 수들 뿐이다. 이러한 생각에 착안하여 앞자리는 두 자리 수 중 끝자리가 2인수+1인수+0인수임을 알 수 있다. 이것이 바로 동적프로그래밍을 적용하는데 있어 전단계와 다음 단계 간의 연결고리이다. 이와 같이 arr[i][j]에는 i자릿수 중 끝자리가 j인 경우의 수를 담는다. 그 후 해당 행의 값들을 모두 더해주면 해당 행만큼의 자릿수를 가진 수의 가짓수가 나온다.

 

코드

---

# 백준 11057

n = int(input())
arr = [[0]*10 for _ in range(1001)]
for i in range(10):
    arr[1][i] = 1
for i in range(2, n+1):
    for j in range(10):
        for k in range(j+1):
            arr[i][j] += arr[i-1][k]
print(sum(arr[n])%10007)