[210520][백준/BOJ] 11057번 오르막 수

문제

입출력

풀이

d[n][L]에서 숫자 L은 이전값보다 크거나 같아야 한다.
백준 10844번을 푸는 방식에서 k=j부터 시작하는 3중 for문을 사용하면 이전값보다 크거나 같은 값들의 개수를 구할 수 있다.
또한 이전 자리수의 값들을 누적해서 더해줘야 한다.

즉 수의 길이가 2이고 값이 1이라면 수의 길이가 1인 경우의 수와 수의 길이가 2이면서 앞자리수가 1부터 9까지인 경우의 수를 모두 더해줘야 한다.

따라서 점화식은

d[i][j] = d[i][j] + d[i-1][k]

다음과 같다.

코드

#include <bits/stdc++.h>
using namespace std;
#define MOD 10007

int d[1002][1002];
int dp(int n)
{
	for (int i = 0; i < 10; ++i)
		d[1][i] = 1;

	for (int i = 2; i <= n; ++i)
	{
		for (int j = 0; j <= 9; ++j)
		{
			for (int k = j; k <= 9; ++k)
			{
				d[i][j] = (d[i][j] + d[i - 1][k]) % MOD;
			}
		}
	}

	int sum = 0;
	for (int i = 0; i < 10; ++i)
		sum = (sum + d[n][i]) % MOD;
	return sum;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n;
	cin >> n;

	cout << dp(n);
}