[C++] 백준 11057번 오르막 수

 

1) 문제설명

백준 Online Judge 11057번 오르막 수

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

11057번: 오르막 수

 

2) 아이디어

전에 풀었던 쉬운 계단 수와 비슷한 문제이다.

https://kiveiru.tistory.com/16?category=557953 

[C++] 백준 10844번 쉬운 계단 수

 

DP의 정의를 DP [자릿수][마지막 수] = 가능한 수의 개수로 설정하고 점화식을 세우기 위해 표를 만들어서 규칙을 찾는다.

한자리 수일 때는 모두 0~9까지 하나씩밖에 올 수 없기 때문에 가능한 수의 개수는 1씩 할당된다.

두 자릿수일 때는

마지막 수가 0일 때 : 00

마지막 수가 1일 때 : 01, 11

마지막 수가 2일 때 : 02, 12, 22

...

세 자릿수 일 때는

마지막 수가 0일 때 : 000

마지막 수가 1일 때 : 001, 011, 111

마지막 수가 2일 때 : 002, 012, 022, 112, 122, 222

...

이런 식으로 세어서 표를 만든다. DP [자릿수][마지막수]의 규칙은 = DP [자릿수][마지막수-1]+ DP [자릿수-1][마지막수] 임을 알 수 있다.

자릿수/ 마지막수	1	2	3	4	5	6	7	8	9	0
1	1	1	1	1	1	1	1	1	1	1
2	2	3	4	5	6	7	8	9	10	1
3	3	6	10	15	21	28	36	45	55	1

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
long long dp[1001][11]; // dp[자릿수][마지막수]
int main() {
	int n;
	long long sum = 0;
	cin >> n;

	for (int i = 0; i < 10; i++) {
		dp[1][i] = 1; // 자릿수가 1일때
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 1) {
				dp[i][j] = (dp[i - 1][j] + 1) % 10007;
			}
			else {
				dp[i][j] = (dp[i][j - 1] + dp[i - 1][j]) % 10007;
			}
		}
	}
	for (int i = 0; i <= 9; i++) {
		sum = (sum + dp[n][i]) % 10007; // n자릿수의 0~9까지 가능한 수의 갯수를 전부 더한다.
	}
	cout << sum;
	
}