11057_오르막수

▶실버1

풀이

처음에는 왜 dp인지 이해가 가지 않음 -> 모든 수를 탐색하며 오르막 수인지 확인하는 작업을 하기엔 시간이 너무 많이 걸리기 때문에 dp로 처리

만약 0_ _이면 한 자리가 추가될 때 0 0 _ _ (1가지) 만 가능

1 _ _이면 0 1 _ _, 1 1 _ _ (2가지) 가능

....

9 _ _이면 0 9 _ _, 1 9 _ _, ~ , 9 9 _ _ (10가지) 가능

이런 식으로 생각하면 자릿수와 맨 앞 자리의 수가 무엇인지를 따져 `dp[i][j] : 맨 앞 자리 수가 j인 i자리의 수의 개수` 로 놓는다.

ex) 3자리 수 오르막 수 구하기

3자리 수의 오르막 수의 개수를 구하기 위해서는 dp[3][0] + dp[3][1] + ... + dp[3][9] 을 구하면 되는데

dp[3][0] = dp[2][0]

dp[3][1] = dp[2][0] + dp[2][1]

...

dp[3][9] = dp[2][0] + dp[2][1] + ... + dp[2][9] 이다.

이런식으로 1자리수부터 n자리수까지의 dp값을 모두 더하면 n자리수의 오르막 수의 개수를 알 수 있다.

이때 기저조건은 dp[1][0 ~ 9] = 1이다.

 

코드

#include <iostream>
#include <cmath>
#include <algorithm>
using namespace std;

int dp[1001][10];
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int n;
	int sum = 0;
	cin >> n;

	//한 자리 수에는 모두 1
	for (int i = 0; i < 10; i++) {
		dp[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 10; j++) {
			for (int k = j; k < 10; k++) {
				dp[i][j] += dp[i - 1][k];
			}
            //dp값이 커질 수 있기 때문에 나머지를 저장
			dp[i][j] %= 10007;
		}
	}
	
	for (int i = 0; i < 10; i++) {
		sum += dp[n][i];
        //문제에서 10007의 나머지가 답이라고 했기 때문에 10007로 나눈 나머지 값이 최종 답
		sum %= 10007;
	}
	cout << sum;
}