[BOJ 11057] 오르막 수

이 문제는 이곳에서 확인할 수 있습니다.

이 문제는 자리수가 주어질 때, 오르막 수가 몇개인지 구하는 문제입니다.
여기서 오르막 수는 높은 자리수의 수가 낮은 자리수의 수보다 크거나 같은 수를 말합니다.

DP(Dynamic Programming) 문제로서 점화식만 구할 수 있다면 아주 쉽게 풀 수 있는 문제입니다.
이러한 유형의 문제를 풀 때 중요한 것은 답을 구하는데 나타나는 공통점, 일반항을 찾는 것이 중요합니다.

이 문제는 아래와 같이 점화식을 유추해볼 수 있습니다.

1자리수
  0~9
2자리수
  0 0~9
  1 1~9
  .
  .
  7 7~9
  .
  .
  9 9~9
3자리수
  0 0 0~9
    1 1~9
  .
  5 7 7~9
  .
  .
  9 9 9

2자리수 오르막 수인 7 7~9는 3자리수 오르막 수인 5 7 7~9를 만드는데도 사용되고 있습니다. 5 뿐만 아니라 7보다 작거나 같은 0~7까지 모두 7 7~9를 사용하고 있음을 알 수 있습니다.

즉, i자리수를 가지고 마지막 숫자가 j인 수의 오르막 수는 i-1자리수를 가지고 마지막 숫자가 j보다 작거나 같은 수의 오르막 수의 합으로 유추할 수 있습니다.

dp[i][j] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2] + . . . + dp[i-1][j] 

따라서 1의 자리수부터 시작하여 자리수를 확장해가는 Bottom-Up방식으로 문제를 해결할 수 있습니다.

문제에서 오르막 수를 10,007로 나눈 나머지를 요구하고 있으므로 잊지 않고 나눠주는 주도록 합시다!