[백준] 11057번 오르막 수

11057번: 오르막 수

수의 길이가 증가할 때마다 고정되어 있는 것은 수의 맨 뒷자리이므로

맨 뒷자리를 기준으로 표를 그려보면

 

한 자릿수일 때

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

 

두 자릿수일 때

0	1	2	3	4	5	6	7	8	9
00	01	02	03	04	05	06	07	08	09
	11	12	13	14	15	16	17	18	19
		22	23	24	25	26	27	28	29
			33	34	35	36	37	38	39
				44	45	46	47	48	49
					...	...	...	...	...

 

세 자릿수일 때

0	1	2	3	4	5	6	7	8	9
000	001	002	003	004	005	006	007	008	009
	011	012	013	014	015	016	017	018	019
	111	112	113	114	115	116	117	118	119
		022	023	024	025	026	027	028	029
		122	123	124	125	126	127	128	129
		222	223	224	225	226	227	228	229
			...	...	...	...	...	...	...

 

이렇게 나타낼 수 있다.

표시된 부분을 예로 들자면

세 자릿수일 때 맨 뒷자리가 2인 경우는

세 자릿수일 때 맨 뒷자리가 1인 경우 + 두 자릿수일 때 맨 뒷자리가 2인 경우

이다.

 

여기서 필요한 것은 경우의 수이기 때문에

이차원 배열 DP를 만들어 첫 번째 인덱스는 자릿수, 두 번째 인덱스는 맨 뒷자리 숫자로 정하고

자릿수와 맨 뒷자리 숫자에 따른 경우의 수를 값으로 넣어주면

DP[i][j]=DP[i][j-1]+DP[i-1][j]

이라는 규칙을 도출해낼 수 있다.

이대로 구현하면 풀린다

#include <iostream>
using namespace std;
int main() {
	int N;
	cin >> N;
	int dp[1001][10] = { 0 };
	for (int i = 0; i < 10; i++) dp[0][i] = 1;
	for (int i = 1; i < N; i++) {
		dp[i][0] = 1;
		for (int j = 1; j < 10; j++) {
			dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 10007;
		}
	}
	int sum = 0;
	for (int i = 0; i < 10; i++) sum += dp[N - 1][i];
	cout << sum % 10007;
	return 0;
}