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

오늘은 백준11057번 오르막 수 문제를 풀어보도록 하자.

전형적인 DP문제이다.

문제는 다음과 같다.

                               [접근법]

  1. 우선 dp[0][1] ~ dp[9][1]까지 1로 초기화 시켜줍니다. (모두 1가지 씩이므로)
  
  2. 생각해보면 dp[0][2]는 2자리 수이면서 처음에 0으로 시작하는 오르막 수이다. 00 ~ 09까지 있을 수 있고 이는 dp[0][1] ~ dp[9][1]을 
     모두 더해주면 된다. dp[1][2]는 2자리 수이면서 처음에 1로 시작하는 오르막 수이다. 11~19까지 있을 수 있고 dp[1][1] ~ dp[9][1]까지 
     더하면 된다. 이 쯤 하면 어느정도 점화식이 보일 것이다.
  
  3. 주의해야 할 점은 모듈러 연산이다. dp배열에 넣을 때 계속 10007로 나눈 나머지 값을 넣어주는 것과 답을 누적할 때도 10007을 계속
  나눈 나머지 값을 넣는다는 것을 주의하자.

                                     [코드]
#include <iostream>
using namespace std;

int dp[10][1001];
int N,result = 0;

int main() {
	cin >> N;

	for (int i = 0; i < 10; i++){
		dp[i][1] = 1;// Base
	}

	for (int i = 2; i <= 1000; i++) {//
		for (int j = 0; j < 10; j++) {
			for (int k = j; k < 10; k++) {
				dp[j][i] += dp[k][i - 1] % 10007;
			}
		}
	}
	for (int i = 0; i < 10; i++) {
		result += dp[i][N] % 10007;
		result %= 10007;
	}
	cout << result << '\n';
}