[BOJ/C++] 11057번 오르막수

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

1. 수의 길이 입력받기

2. 자릿수내 오름차순 수의 개수 구하기 (n=2라면 0~99)

 

오르막 수의 개수를 구하는 가장 쉬운 방법은 그 수를 하나하나 체크하는 것이다 그러나 하나하나 체크하려면 10^n개의 수의 n자리 수를 확인해야한다 시간초과 걸리기 딱 좋음!!

시간복잡도를 고려해봤을 때 DP(다이나믹 프로그래밍)을 생각해볼 수 있다 (bottom up 방식으로 미리 작은것부터 구하기)

아래와 같이 표를 그려 가지수를 생각해보자

마지막 수	0	1	2	3	4	5	6	7	8	9
n=1	1	1	1	1	1	1	1	1	1	1
n=2	1 (X0)	2 (X1)	3	4	5	6	7	8	9	10
n=3	1(XX0)	3(XX1)	6(XX2)	10	15	21	28	36	45	55

 

n=i일때 마지막 수가 j인 오름수의 개수는 (n=i-1이고 마지막 수가 j인 오름수의 개수) + (n=i이고 마지막수가 j-1인 오름수의 개수)와 같다는걸 알 수 있다 (j가 1인 경우를 제외)

 

이를 이용해서 코드를 짜면 아래와 같다!!

 

#include <iostream>

using namespace std;
int cnt[1001][10] = {0};

int result(int n)
{
    long long count = 0;

    if (n == 1)
        return 10;

    for (int j = 2; j <= n; j++)
    {

        for (int i = 0; i < 10; i++)
        {

            cnt[j][i] = cnt[j - 1][i]; // n자리가 i이기전까지 경우의 수
            if (i > 0)
            {
                cnt[j][i] += cnt[j][i - 1];
            }

            cnt[j][i] %= 10007;
        }
    }

    for (int i = 0; i < 10; i++)
    {
        count += cnt[n][i];
        // cout << cnt[n][i] << "\n";
    }

    return count % 10007;
}

int main()
{
    int n;
    cin >> n;

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

    cout << result(n);
}