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

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

2688번: 줄어들지 않아

n이 1일 때, 가능한 경우는 (1,2,3,4,5,6,7,8,9) 총 10가지입니다.

n이 2라면, 가능한 경우는 (11...19, 22...29, 33...39, 44...49, ... 99)로 총 55가지입니다.

n이 3일때는 n이 2일 때 나온 모든 경우의 앞자리에 조건에 충족하는 수(맨 앞자리 이상인 수)를 붙였을 때의 모든 경우일 것입니다.

(어휘가 부족해 말이 이상한데, 예를 들어 34 앞에는 0~3의 수가 붙을 수 있습니다. - 034, 134, 234, 334)

 

따라서, 각각의 n에서의 0~9로 끝나는 경우의 수를 갖고 있는 테이블을 그리면 답을 구할 수 있습니다.

 

1 1 1 1 1 1 1 1 1 1
10 9 8 7 6 5 4 3 2 1
55 45 36 28 21 15 10 6 3 1
220 165 120 84 56 35 20 10 4 1

0	1	2	3	4	5	6	7	8	9
1	1	1	1	1	1	1	1	1	1
10	9	8	7	6	5	4	3	2	1
55	45	36	28	21	15	10	6	3	1
220	165	120	84	56	35	20	10	4	1

(티스토리에서 제공하는 테이블 기본값 최대 크기가 10*10이라 n은 생략했습니다..)

 

위 테이블을 dp[i][j]라 할 때, j=0일때는 dp[i-1]의 총합입니다. (n-1의 모든 경우에 대해서 0을 앞에 붙일 수 있으므로)

j=i일때는 j=0~i-1인 경우를 제외한 모든 경우에 붙일 수 있으므로 dp[i][j-1]에 dp[i-1][j-1]을 뺀 값입니다.

 

위와 같은 dp table을 그린 후, 입력받은 n행의 총합이 답이 됩니다.

#include<iostream>
using namespace std;

int main(){
	ios_base :: sync_with_stdio(false); 
	cin.tie(NULL); 
	cout.tie(NULL);
	
	long long int n, t, dp[65][10], ans[65]={0,10};
	
	for(int i=0; i<10; i++){
		dp[1][i]=1;
	}
	
	for(int i=2; i<=64; i++){
		dp[i][0] = ans[i-1];
		ans[i]+=dp[i][0];
		for(int j=1; j<10; j++){
			dp[i][j] = dp[i][j-1]-dp[i-1][j-1];
			ans[i]+=dp[i][j];
		}
	}
	cin>>t;
	while(t--){
		cin>>n; 
		cout<<ans[n]<<'\n';
	}
}