[BAEKJOON] 11057 오르막 오르기

자리수		0으로시작	1로시작	2로시작	3으로시작	4로시작	5로시작	6으로시작	7로시작	8로시작	9로시작	합	출력
1		1	1	1	1	1	1	1	1	1	1	10	10
2		10	9	8	7	6	5	4	3	2	1	55	55
3		55	45	36	28	21	15	10	6	3	1	220	220
4		220	165	120	84	56	35	20	10	4	1	715	715
5		715	495	330	210	126	70	35	15	5	1	2002	2002
6		2002	1287	792	462	252	126	56	21	6	1	5005	5005
7		5005	3003	1716	924	462	210	84	28	7	1	11440	1433
8		11440	6435	3432	1716	792	330	120	36	8	1	24310	4296
9		24310	12870	6435	3003	1287	495	165	45	9	1	48620	8592
10		48620	24310	11440	5005	2002	715	220	55	10	1	92378	2315
11		92378	43758	19448	8008	3003	1001	286	66	11	1	167960	7848
12		167960	75582	31824	12376	4368	1365	364	78	12	1	293930	3727
13		293930	125970	50388	18564	6188	1820	455	91	13	1	497420	7077
14		497420	203490	77520	27132	8568	2380	560	105	14	1	817190	6623
15		817190	319770	116280	38760	11628	3060	680	120	15	1	1307504	6594
16		1307504	490314	170544	54264	15504	3876	816	136	16	1	2042975	1547
17		2042975	735471	245157	74613	20349	4845	969	153	17	1	3124550	2366
18		3124550	1081575	346104	100947	26334	5985	1140	171	18	1	4686825	3549
19		4686825	1562275	480700	134596	33649	7315	1330	190	19	1	6906900	2070
20		6906900	2220075	657800	177100	42504	8855	1540	210	20	1	10015005	8005
21		10015005	3108105	888030	230230	53130	10626	1771	231	21	1	14307150	7147
22		14307150	4292145	1184040	296010	65780	12650	2024	253	22	1	20160075	5977
23		20160075	5852925	1560780	376740	80730	14950	2300	276	23	1	28048800	9186
24		28048800	7888725	2035800	475020	98280	17550	2600	300	24	1	38567100	122
25		38567100	1.1E+07	2629575	593775	118755	20475	2925	325	25	1	52451256	4569
26		52451256	1.4E+07	3365856	736281	142506	23751	3276	351	26	1	70607460	8075

출처 : https://www.acmicpc.net/problem/11057

이렇게 나온다 이유는 

두 자리 숫자를 만든다고 가정했을 때

맨 첫 번째 자리 숫자가 0 : 0~9 => 10

맨 첫 번째 자리 숫자가 1 : 1~9 => 9

...

맨 첫 번째 자리 숫자가 9 : 9 => 1

세 자리 숫자를 만든다고 가정했을 때

맨 첫 번째 자리 숫자가 0 -> 다음 숫자는 2자리 숫자의 0부터 9까지가 들어갈 수 있음 

즉 위에서 구한 2자리 숫자의 모든 경우의 수를 더해주면 됨

#include <iostream> #include <vector> using namespace std; vector<vector<int>>map; int main() { map = vector<vector<int>>(10001, vector<int>(10, 0)); //자리수, 시작하는 숫자 for (int y = 0; y < 10; y++) map[1][y] = 1; for (int x = 2; x < 10001; x++) { map[x][9] = 1; for (int y = 9; y > 0; y--) { map[x][y - 1] = (map[x][y] + map[x - 1][y - 1]) % 10007; } } int num, ans = 0; cin >> num; for (int k = 0; k < 10; k++) ans = (ans + map[num][k]) % 10007; cout << ans << endl; }