문제

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

---

풀이

0000
0011
1111
1112
1122
2223
...

단조 증가하는 n자리 수열의 개수를 구하는 문제이다.

예시를 통해 가능한 경우의 수를 일일이 구해봤는데 너무 많이 나오는 거 같아서

전체 경우의 수에서 감소하는 수열의 개수를 빼서 구해볼까? 라는 생각이 들었다.

그래서 감소하는 수열 개수의 규칙성을 파악해보려고 노트에 끄적여봤으나... 4자리 수열에 대해 715라는 경우의 수가 도저히 나오질 않았다.

갈피를 못잡고 결국 답을 봤는데 dp를 사용하는 문제였다.

dp[i][j]: i번째 자리수가 j일 때, 가능한 단조 증가 수열의 개수

위처럼 정의한 dp 테이블에 작은 문제들의 해를 저장해두면, 이것을 모아서 큰 문제를 해결할 수 있다. 그리고 부분 문제를 구하는 방법은 중복된다.

1. 최적 부분 구조
2. 중복되는 부분 문제

즉, 위의 두 가지를 만족시키면 dp로 해결할 수 있는 문제라고 판단할 수 있다. 이번 문제도 마찬가지이다.

왜 그런지 예시를 통해 이해해보자!

우선 dp[1][j] (0 <= j <= 9) 는 1로 초기화 해야 한다. 첫번째 자리수보다 더 낮은 자리수는 없기 때문이다.

dp[2][j]는 어떨까?

dp[2][0] 일때, 가능한 단조 증가 수열은 다음과 같다.

00, 01, 02, ..., 09

그리고 그 개수는 dp[1][0] + dp[1][1] + ... + dp[1][9] = dp[1][j] (0 <= j <= 9) 와 동일하다.

dp[2][4] 일때, 가능한 단조 증가 수열은 다음과 같다.

44, 45, ..., 49

그리고 그 개수는 dp[1][4] + dp[1][5] + ... + dp[1][9] = dp[1][j] (4 <= j <= 9) 와 동일하다.

즉, 이러한 규칙성을 일반화 시킨 점화식은 다음과 같다.

dp[i][j] += dp[i - 1][k] (j <= k <= 9)

C++ 코드

#include <iostream>
#include <string> 
#include <cstring>
#include <sstream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <stack>
#include <queue>
#include <map>
#include <set>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

int t, n;
ll dp[65][10]; // i번째 자리수가 j일 때 

void fillTable(){
	for(int i = 0; i <= 9; i++){
		dp[1][i] = 1; 
	}

	for(int i = 2; i <= 64; i++){ // i번째 자리수가
		for(int j = 0; j <= 9; j++){ // j일 때
			// 가능한 단조 증가 수열의 개수를 
			// 부분 문제의 해를 모아서 구한다. 
			for(int k = j; k <= 9; k++)
				dp[i][j] += dp[i - 1][k];
		}
	}
}

void solution(){
	// n번째 자리수가 0~9일 때 
	// 가능한 단조 증가 수열의 개수 
	ll ans = 0;
	for(int i = 0; i <= 9; i++){
		ans += dp[n][i];
	}
	cout << ans << "\n";
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	fillTable();

	cin >> t;
	while(t--){
		cin >> n; 
		solution(); 
	}
	
	return 0;
}