[boj : 2688] 줄어들지 않아

www.acmicpc.net/problem/2688

2688번: 줄어들지 않아

문제 : n자리 수가 주어지고 처음부터 끝까지 각 숫자들이 줄어들지 않는 수의 개수를 구해라

 

풀이 : 하나씩 살펴보자

n=1 -> 0 1 2 3 4 5 6 7 8 9 : 10개

n=2 -> 00 01 02 03 04 05 06 07 ~~~ 99 : (10+9+~~+2+1)55개

이것만 봐도 규칙이 바로 보인다. 

0이 붙어지게 되면 다음은 0부터 9까지 붙을수가 있고

9가 붙어지게 되면 다음은 9 하나만 붙을 수 있다.

 

이를 점화식으로 표현하려고 해보면 일단 각 자리를 표현할 수 있는 변수 하나, 0~9까지 수가 들어갈 수 있다는 걸 표현하는 변수 하나

즉, 이차원 배열로 테이블을 표현할 수 있다.

 

dp[i][j] = i 자리에 j 숫자까지 들어갈 수 있는 경우의 수

 

 

이렇게 표현을 해줄 수 있겠다.

그럼 줄어들지 않은 n자리수의 개수는 저 행을 전부 더해주면 된다.

#include<bits/stdc++.h>

using namespace std;
using ll = long long;

ll dp[66][10];

ll f(int x, int y);

int main()
{
	int t;
	cin >> t;
	
	memset(dp, -1, sizeof(dp));
	for (int i = 0; i < 10; i++)
		dp[1][i] = 1;
	f(65, 9);
	int n;
	for (int i = 0; i < t; i++) {
		ll sum = 0;
		cin >> n;
		for (int j = 0; j < 10; j++)
			sum += dp[n][j];
		cout << sum << "\n";
	}
	return 0;
}
ll f(int x, int y)
{
	if (x <= 0)return 0;
	ll &ret = dp[x][y];
	if (ret != -1)return ret;

	ret = 0;
	for (int i = y; i >= 0; i--)
		ret += f(x - 1, i);
	return ret;
}

이때 주의할 점은 한줄 위부터 시작하니 행의 수는 65칸으로 잡아주자