[2668번] 줄어들지 않아

www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

풀이

dp[n][k]: k로 시작하는 n자리 수

 

하나씩 써보며 규칙을 찾아본다면,

 

dp[1][0] = dp[1][1] = dp[1][2] = dp[1][3] = dp[1][4] = dp[1][5] = dp[1][6] = dp[1][7] = dp[1][8] = dp[1][9]=1

n=1일 때는 모두 1로 저장한다.

 

n=2일 때부터 다시 규칙을 찾아본다면,

dp[2][0] = dp[1][0] + dp[1][1] + ... + dp[1][9]

dp[2][1] = dp[1][1] + dp[1][2] + ... + dp[1][9]

...

dp[2][9] = dp[1][9]

 

n=3

dp[3][0] = dp[2][0] + dp[2][1] + ... + dp[2][9]

dp[3][1] = dp[2][1] + dp[2][2] + ... + dp[2][9]

...

dp[3][9] = dp[2][9]

 

다음과 같이 dp[n][k] = dp[n-1][k] + dp[n-1][k+1] + ... + dp[n-1][9] 가 성립하게 된다.

dp[n][k]를 "k로 시작하는 n자리 수"로 정의하여 문제를 해결하였지만, 

"k로 끝나는 n자리 수"로 정의하고 문제를 풀어도 동일한 결과가 나옴을 알 수 있다.

 

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;

int t;
vector<int> v;
long long dp[65][10];
long long result[65]; // 줄어들지 않는 n자리 수의 개수

int main() {

	memset(dp, -1, sizeof(dp));
	cin >> t;

	int max_num = -1;
	for (int i = 0;i < t;i++) {
		int k;
		cin >> k;
		v.push_back(k);
		max_num = max(max_num, k);
	}

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

	result[1] = 10;
	for (int i = 2;i <= max_num;i++) {
		result[i] = 0;
		for (int j = 0;j < 10;j++) {
			dp[i][j] = 0;  
			for (int k = j;k < 10;k++) {
				dp[i][j] += dp[i - 1][k];
			}
			result[i] += dp[i][j];
		}
	}

	for (int i = 0;i < t;i++) {
		cout << result[v[i]] << endl;
	}
}