백준 11057번 오르막 수 C++

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

다이나믹 프로그래밍으로 해결할 수 있는 문제이다.

 

dp 테이블을 보면서 설명을 해보자면, 우선 행은 숫자의 길이이고 열은 맨 앞의 숫자이다.

문제에도 나와있듯이 숫자는 0으로 시작할 수 있다.

길이가 0개인 숫자는 없으니 0행은 모두 0이고,

길이가 1개인 숫자는 맨 앞 숫자가 무엇이든 1개이니 1행은 모두 1이다.

2행부터 살펴보자면, 우선 시작 숫자가 9이면 가능한 숫자는 99 하나밖에 없다. 그래서 9열은 우선 1로 채워준다.

그 다음부터는, 예를들어 7열을 보면 77,78,79가 가능한데, 이것을 1행과 연관지어서 생각해보면

1행의 7,8,9열은 길이가 1이고 시작하는 숫자가 7,8,9인 숫자들이기 때문에 당연히 7 뒤에 붙어셔 2자리 오르막 수로 만들 수 있다. 그래서 2행의 7열은 1행의 7,8,9열을 더한 값이 된다.

 

다시 그림으로 살펴보면 이렇게 된다.

그리고 6열 또한 1행의 6,7,8,9열을 더한 값인데, 여기서 7,8,9열을 더한 값은 이미 2행7열에 저장이 되어있다.

그래서 2행의 6열은 1행의 6열과 2행의 7열을 더한 값이 된다.

 

이것을 그림으로 나타내면 이렇게 되고

여기서 나오는 점화식은 dp[i][j]=dp[i-1][j]+dp[i][j+1] 이다.

최종 답은 n행의 모든 열을 더하면 된다. ( 0~9에서 시작하는 모든 값들을 구해야 하기 때문에)

문제에서 답을 10007로 나눈 나머지를 출력하라고 했기 때문에 코드에서도 계속 나머지를 구해주었다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	ll n;
	cin >> n;
	vector<vector<ll>> dp(n + 1, vector<ll>(10, 0));

	for (int i = 1; i <= n; i++) {
		for (int j = 9; j >= 0; j--) {
			if (j == 9) {
				dp[i][j] = 1;
				continue;
			}
			dp[i][j] = (dp[i][j + 1] % 10007) + (dp[i - 1][j] % 10007);
			dp[i][j] %= 10007;
		}
	}
	ll sum = 0;
	for (int i = 0; i < 10; i++) {
		sum += dp[n][i] % 10007;
		sum %= 10007;
	}
	cout << sum;
};