[BAE/<JOON> 문제풀이] 2668. 줄어들지 않아

www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

서론 ||

고층 빌딩 거의 다 풀었는데 계수찾는 점화식을 몰라서 못풀고 있다..

 

풀이 ||

점화식도 간단하고 떠올리기도 어렵지 않다.

 

현재 숫자의 첫자리앞에 자릿수를 늘려서 새로운 수를 만들면 그 수는 현재 숫자까지의 모든 줄어들지 않는 수를 포함하게된다.

 

예제로 설명하면 현재 숫자가 321이고 앞에 4를 붙여서 4321이라는 숫자를 만들 수 있다.

 

그럼 321이하의 모든 줄어들지 않는 수들은 앞에 4를 붙여 4XXX형식으로 새로운 줄어들지 않는 수가 될 수 있다.

 

즉, 321이하의 모든 수들은 4XXX형태에 추가된다.

 

이를 이용해서 다음과 같은 점화식을 세울 수 있다.

 

점화식 ||

1자리에 줄어들지 않는 수는 총 10개. 0, 1, 2, 3, 4, 5, 6, 7, 8, 9다.

 

이 앞에 새로운 숫자를 붙여 2자리의 줄어들지 않는 수를 만들어보자.

 

앞자리가 0인 수는 00하나다.

앞자리가 1인 수는 10, 11 둘이다.

 

최종적으로 1~10까지 더한 합이므로 2자리의 줄어들지 않는 수는 55개이다.

 

3자리수도 마찬가지로 특정 두자릿수 이전의 모든 경우의 수들을 더한 값이다.

 

이런 식으로 64자리수의 경우수를 모두 계산하고 입력과 출력만 반복하면 된다.

 

코드 ||

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

unsigned long long dp[65][11];
int main()
{
	for (int i = 1; i <= 10; i++) {
		dp[1][i] = i;
	}
	for (int i = 2; i <= 64; i++) {
		for (int j = 1; j <= 10; j++) {
			for (int k = 1; k <= j; k++) {
				dp[i][j] += dp[i - 1][k];
			}
		}
	}
	int tc;
	cin >> tc;	
	while (tc--) {
		int n;
		cin >> n;
		cout << dp[n][10] << "\n";
	}
	return 0;
}