줄어들지 않아

www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

 

문제

어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다.

예를 들어, 1234는 줄어들지 않는다. 

이 문제에서는 숫자의 앞에 0(leading zero)이 있어도 된다. 0000, 0001, 0002는 올바른 줄어들지 않는 4자리수이다.

 

N = 1 (1자리수)

0	1	2	3	4	5	6	7	8	9
1	2	3	4	5	6	7	8	9	10

 계산을 위해 n = 1일 때를 이렇게 채워둔다

 

N = 2 (2자리수)

0	1	2	3	4	5	6	7	8	9
1	3	6	10	15	21	28	36	45	55

dp[2][0] = 1

dp[2][1] = 1 + 2

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

....

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

 

 

N = 3 (3자리수)

0	1	2	3	4	5	6	7	8	9
1	4	10	20	35	56	84	120	165	220

dp[3][0] = 1

dp[3][1] = 1 + 3

dp[3][2] = 1 + 3 + 6

...

dp[3][9] = 1 + 3 + 6 + ... + 45 + 55

 

 

이를 통해 유추하면은

dp[n][j] 를 구하려면 dp[n-1][0] + dp[n-1][1] + .... + dp[n-1][j-1] + dp[n-1][j] 를 해줘야 하는 걸 알수있다.

 

dp[64][10] 

 

코드

#include <iostream>
#include <vector>

using namespace std;

typedef long long ll;
vector<int> vec;
vector<int> vec2;


int main()
{
	int N;
	cin >> N;

	ll dp[64][10] = { 0, };

	// n = 2
	for (int i = 1; i <= 10; i++) {
		vec.push_back(i);
	}

	/*for (int i = 0; i < 10; i++) {
		cout << vec[i] << " ";
	}*/

	for (int i = 0; i < 10; i++) {
		dp[0][i] = i + 1;
	}
	//cout << endl;
	for (int j = 1; j < 64; j++) {
		for (int i = 0; i < 10; i++) {
			int i2 = i;
			//cout << "j : " << j << " i : " << i << endl;

			while (i2 >= 0) {
				dp[j][i] += dp[j - 1][i2];
				i2--;
			}
		}


	}

	for (int i = 0; i < 64; i++) {
		for (int j = 0; j < 10; j++) {
			cout << dp[i][j] << " ";
		}
		cout << endl;
	}

	int num;
	for (int i = 0; i < N; i++) {
		cin >> num;
		vec2.push_back(num);
	}

	for (int i = 0; i < size(vec2); i++) {
		cout << dp[vec2[i] - 1][9] << endl;
	}

}