[BOJ] 문제 11057 오르막 수 (dp문제)

 

문제 이해

 

N 이라는 자릿수가 주어졌을 때, 가장 앞자리 수부터 ~ N 까지의 수가 오름차순으로 이루어져 있어야 한다.

 

 

문제 풀이

 

N 이 2 이상일 때, k = 9의 경우는 항상 1. 99, 999, 999...

N 이 2 이상일 때, k < 8 의 값은 dp[N-1][k] + dp[N-1][K+1, K+2.... 8];

 

주의사항

 

첫 시작 수는 0부터 시작한다.

0으로 시작하는 수의 n=2 값의 경우 00, 01, 02, 03, 04... 는 n=1 값의 1, 2, 3, 4.. 와는 다르다.

끝자리가 9가 되면 더이상의 오름차순은 불가능해진다.

111, 222, 333, 22223 과 같은 중복수가 가능해진다.

 

 

결과

bottom-up

 

top-down