백준2688 - 줄어들지 않아

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

2688번: 줄어들지 않아

2차원 DP를 사용하여 푼 문제였다. mat[i][j]를 이용하여 i개의 숫자가 주어질 때 j가 맨 앞자리라면 올 수 있는 수열의 갯수를 구하는 방법으로 풀었다. 규칙은 다음과 같다.

 

한자리

0 ~ 9 -> 10개

총 10개

 

두자리

00 ~ 09 -> 10개 (한자리 경우에서  0 ~ 9의 합)

11~19 -> 9개 (한자리 경우에서 1 ~ 9의 합)

22~29 -> 8개 (한자리 경우에서 2 ~ 9의 합)

.

.

.

88 ~ 89 : 2개 (한자리 경우에서 8~ 9의 합)

99 : 1개 (한자리 경우에서 9 ~ 9의 합)

총 55개

 

세자리

000 ~ 099 -> 55개 (두자리 경우에서 00 ~ 99의 합)

111 ~ 199 -> 45개 (두자리 경우에서 11 ~ 99의 합)

222 ~ 299 -> 36개 (두자리 경우에서 22 ~ 99의 합)

333 ~ 399 -> 28개 (두자리 경우에서 33 ~ 99의 합)

.

.

.

888 ~ 899 -> 3개 (두자리 경우에서 88 ~ 89의 합)

999 -> 1개 (두자리 경우에서 99 ~ 99의 합)

총 715개

 

규칙을 보면 mat[i][j]는 mat[i - 1][9] ~ mat[i - 1][j]의 합을 구한 결과이다. 또한 맨 앞자리가 9로 끝나면 경우의 수는 무조건 1개이다. 

 

#include <iostream>
using namespace std;

long long int mat[65][10] = { 0, }; //64자리 모든 경우의 맨 앞의 올 수 있는 10가지의 숫자를 수열로 나열한 결과
long long int res[65]; //64자리 모두의 결과를 담을 공간

void func() {
	for (int i = 0; i <= 64; i++) {
		mat[i][9] = 1; //맨 앞자리가 9인 경우, 수열은 1가지만 존재한다.
	}

	for (int i = 1; i <= 64; i++) {
		for (int j = 8; j >= 0; j--) { //큰 수에서 작은 수로 결과를 도출하였다.
			mat[i][j] = mat[i - 1][j] + mat[i][j + 1]; //mat[i - 1][9] ~ mat[i - 1][j]까지의 합
		}
	}

	for (int i = 0; i <= 64; i++) {
		long long int sum = 0; //i자리일 때 결과의 합을 구할 변수
		for (int j = 0; j <= 9; j++) {
			sum = sum + mat[i][j]; //j가 맨 앞에 올 때의 가짓수를 더한다.
		}
		res[i] = sum; //i자리일 때 결과를 초기화
	}
}

int main() {
	int n, num;

	func();

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> num;
		cout << res[num] << '\n';
	}
}