[백준 2688번 / C++] 줄어들지 않아

dp를 활용한 문제이다. 

 

#접근방법

 

제일 먼저 생각해야하는 것은 각 자릿수를 나타내는 dp배열을 생성해야한다.

 

예를 들어, 

 

dp[1][3] 은 첫번째 자릿수의 값이 3일 때! 

dp[2][1] 은 두번째 자릿수의 값이 1일 때!

dp[4][0] 은 네번째 자릿수의 값이 0일 때! 

 

그렇기 때문에, 먼저 dp[1][i] 를 1로 초기화 한다. 왜냐하면 첫 번째 자릿수의 각 숫자들은 오로지 하나만 존재할 수 있다. 

 

그리고 dp[2][i] 를 갱신해나가야하는데, 

 

dp[2][0] 이라면 

"00", "01", "02", "03" ..... "08", "09" 의 경우의 수가 있다 즉, dp[1][0]~ dp[1][9]의 합과 같다. 

 

dp[2][4] 라면 

"44", "45", "46", "47", "48", "49" 의 경우의  수가 있다. 즉, dp[1][4]~dp[1][9]의 합과 같다. 

 

즉, 점화식을 구하면 , 

 

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

 

#include <iostream>
using namespace std;
long long dp[65][10]; 
int t, n; 
int main() {

	for (int i = 0; i <= 9; i++)
		dp[1][i] = 1;

	for (int i = 2; i <= 64; i++)
		for (int j = 0; j <= 9; j++)
			for (int k = j; k <= 9; k++)
				dp[i][j] += dp[i - 1][k];

	cin >> t;
	while (t--) {
		cin >> n;
		long long result = 0;
		for (int i = 0; i <= 9; i++)
			result += dp[n][i];
		cout << result << '\n';
	}
}

 

2688번: 줄어들지 않아