백준 11057 - 오르막 수

문제

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

11057번: 오르막 수

 

풀이

N자리 정수가 있을 때, N번째(1의 자리)에 올 수 있는 수는 0~9 이다. 이때 0부터 9까지 각각 N-1의 자리에 올 수 있는 수는 다르다.

N=0 이면 N-1=0 이고,

N=1 이면 N-1=(0, 1)

.......,

N=9 이면 N-1=(0,1,2,3,4,5,6,7,8,9) 가 된다.

 

D[N][L] = N 자리 마지막 수가 L 일 때 오르막 수의 개수 라고 하면, 다음의 점화식을 구할 수 있다. 

D[N][L] = ∑(D[N - 1][i]) (i = 0 ~ L) 이고

∑(D[N][L]) (L = 0 ~ 9) 를 구하면 N 자리 오르막 수의 개수를 구할 수 있다.

 

코드

탑다운 방식

#include <iostream>
 
using namespace std;
 
int N;
int cnt;
 
const int mod = 10007;
 
int dp[1001][10];
 
int f(int N, int L)
{
    if (N == 1) return 1;
    if (dp[N][L]) return dp[N][L];
 
    for (int i = 0; i <= L; i++) dp[N][L] = (dp[N][L] + f(N - 1, i)) % mod;
    return dp[N][L];
}
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    for (int i = 0; i < 10; i++) cnt = (cnt + f(N, i)) % mod;
 
    cout << cnt;
 
    return 0;
}
 

 

바텀업 방식

#include <iostream>
 
using namespace std;
 
int N;
int cnt;
 
const int mod = 10007;
 
int dp[1001][10];
 
int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);
 
    cin >> N;
 
    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 = 0; k <= j; k++)
            {
                dp[i][j] += dp[i - 1][k];
                dp[i][j] %= mod;
            }
        }
    }
 
    for (int i = 0; i < 10; i++) cnt = (cnt + dp[N][i]) % mod;
 
    cout << cnt;
 
    return 0;
}