N자리 감소하지 않는 수(비내림수)의 총 개수 구하기

어떤 수의 모든 자릿수가 바로 앞자리의 숫자보다 작지 않을 때, 그 수를 감소하지 않는 수(non-decreasing number)라고 합니다. 예를 들어 111, 112, 123, 789, 569처럼 왼쪽에서 오른쪽으로 갈수록 숫자가 유지되거나 커지는 수가 여기에 해당합니다. 이 글에서는 N자리 수 전체에서 감소하지 않는 수가 총 몇 개 존재하는지 동적 계획법(DP)으로 구하는 방법을 알아보겠습니다.

길이가 n이고 마지막 자릿수가 d인 감소하지 않는 수의 개수를 세는 함수를 count(n, d)라고 정의하면, 다음과 같은 점화식으로 관계를 나타낼 수 있습니다.

$$count(n,d)=\displaystyle\sum\limits_{i=0}^d count(n-1,i)\\total=\displaystyle\sum\limits_{d=0}^{n-1} count(n-1,d)$$

즉, 마지막 자릿수가 d인 길이 n짜리 감소하지 않는 수는, 길이가 n-1이면서 마지막 자릿수가 d 이하인 모든 감소하지 않는 수 뒤에 d를 붙여 만들 수 있습니다.

입력 및 출력

입력:
자릿수 n, 예를 들어 3.
출력:
가능한 감소하지 않는 수의 총 개수. n이 3일 때는 220.
감소하지 않는 수의 예: 111, 112, 123, 789, 569 등.

알고리즘

countNumbers(n)

입력: 자릿수 n.

출력: n자리 수 중 감소하지 않는 수의 총 개수.

Begin
    define count matrix of order (10 x n+1), and fill with 0
    for i := 0 to 9, do
        count[i, 1] := 1
    done

    for digit := 0 to 9, do
        for len := 2 to n, do
            for x := 0 to digit, do
                count[digit, len] := count[digit, len] + count[x, len-1]
            done
        done
    done

    nonDecNum := 0
    for i := 0 to 9, do
        nonDecNum := nonDecNum + count[i, n]
    done

    return nonDecNum
End

알고리즘 동작 원리

10 × (n+1) 크기의 DP 테이블 count를 만들고 모든 값을 0으로 초기화합니다.
한 자리 수는 항상 감소하지 않는 수이므로 count[i][1] = 1로 설정합니다.
길이를 2부터 n까지 늘려 가며, 마지막 자릿수가 digit인 경우 앞자리가 0부터 digit까지인 모든 경우의 수를 더해 누적합니다.
마지막으로 마지막 자릿수가 0~9인 모든 경우를 합산하여 답을 반환합니다.

C++ 예제 코드

#include<iostream>
using namespace std;

long long int countNumbers(int n) {
    long long int count[10][n+1];   //마지막 자릿수가 i이고 길이가 j인 감소하지 않는 수의 개수 저장

    for(int i = 0; i<10; i++)
        for(int j = 0; j<n+1; j++)
            count[i][j] = 0;        //모든 값을 0으로 초기화

    for (int i = 0; i < 10; i++)    //한 자리 감소하지 않는 수는 각각 1개씩
        count[i][1] = 1;

    for (int digit = 0; digit <= 9; digit++) {      //모든 자릿수 0~9에 대해
        for (int len = 2; len <= n; len++) {        //길이 2부터 n까지
            for (int x = 0; x <= digit; x++)
                count[digit][len] += count[x][len-1];   //앞자리 x(<=digit)인 길이 len-1 경우를 누적
        }
    }

    long long int nonDecNum = 0;

    for (int i = 0; i < 10; i++)    //마지막 자릿수가 0~9인 모든 경우 합산
        nonDecNum += count[i][n];
    return nonDecNum;
}

int main() {
    int n = 3;
    cout << "Enter number of digits: "; cin >> n;
    cout << "Total non decreasing numbers: " << countNumbers(n);
}

실행 결과

Enter number of digits: 3
Total non decreasing numbers: 220

조합론적 해석

흥미롭게도 이 문제는 조합 공식으로도 풀 수 있습니다. n자리 감소하지 않는 수는 0~9의 열 개 숫자에서 중복을 허용해 n개를 오름차순으로 나열하는 것과 같으므로, 그 개수는 중복 조합 C(n+9, 9)와 같습니다. n = 3일 때 C(12, 9) = 220으로, 위 DP 결과와 정확히 일치합니다. 다만 n이 커지면 값이 매우 빠르게 증가하므로, 오버플로우를 방지하려면 long long 타입을 사용하는 것이 좋습니다.