1. 문제
https://www.acmicpc.net/problem/11057
2. 문제 이해
길이가 N이고 원소가 한 자리 수인 단조 증가 수열의 개수를 구하는 문제입니다.
단조 증가 수열은 나중에 나오는 원소가 이전의 원소보다 같거나 큰 수열을 말합니다.
예를 들어 [2, 2, 3, 4]와 [3, 6, 7, 8], [1, 1, 1, 1, 9]는 단조 증가 수열이지만,
[2, 2, 3, 2], [3, 6, 7, 6], [9, 1, 1, 1, 1]은 단조 증가 수열이 아닙니다.
참고로 단조롭다는 표현은 영어로 monotonic으로 사용합니다.
3. 해결 방법
우선 N이 1부터 차례대로 살펴봅시다.
길이가 1인 단조 증가 수열은 [0], [1], [2], [3], [4], [5], [6], [7], [8], [9]로 총 10개입니다.
길이가 2인 단조 증가 수열은 [0, 0], [0, 1], ..., [0, 9], [1, 1], [1, 2], ..., [1, 9], ..., [9, 9]로 총 55개(10+9+...+2+1)입니다.
길이가 3인 단조 증가 수열은 [0, 0, 0], ..., [0, 0, 9], ..., [0, 9, 9], ..., [9, 9, 9]로 총 220개(55+45+...+3+1)입니다.
가. 초기 접근
노가다로 직접 구해보니 규칙이 보입니다.
점화식을 작성해봅시다.
먼저 \(dp(i, \; j)\)를 길이가 \(i\)이고 첫번째 원소가 \(j\)인 단조 증가 수열의 개수라고 정합니다.
그러면 \( dp(i, \; j) = \sum\limits_{k = j}^{9} dp(i-1, \; k) \; (단, \; dp(1, \; n) = 1 \; (0 \le n \le 9)) \)이라고 할 수 있습니다.
DP테이블도 점화식에 맞게 채워봅시다.
나. 개선 방법(역방향 dp)
DP테이블이 채워지는 과정을 보니 비효율적인 과정이 존재합니다.
합을 구하는 과정에서 이전에 구한 값의 일부가 다음 값이 됩니다.
따라서 역방향으로 DP테이블을 채우면 이전의 값을 활용하여 다음 값을 구할 수 있습니다.
점화식을 다음과 같이 수정할 수 있습니다.
\( dp(i, \;j) = dp(i-1, \; j) \; + \;dp(i, \;j+1) \; (단,\; dp(i,\;9) = dp(i-1, \; 9)\;)\)
점화식에 따라 DP테이블을 채우면 다음과 같습니다.
