자릿수의 합이 주어진 값과 같은 숫자의 개수 구하기

자릿수 n과 목표 값(sum)이 주어졌을 때, 각 자릿수의 합이 주어진 값과 정확히 일치하는 모든 n자리 숫자를 찾는 문제입니다. 이때 0은 자릿수로 계산하지 않으며, 첫 번째 자리에는 0이 올 수 없습니다.

제약 조건은 다음과 같습니다.

자릿수 n: 1 이상 100 이하
목표 값: 1 이상 500 이하

입력 및 출력 예시

입력:
자릿수와 목표 합을 입력받습니다.
예를 들어 자릿수가 3이고 합이 15인 경우

출력:
각 자릿수의 합이 15가 되는 서로 다른 3자리 숫자의 개수를 출력합니다.
결과는 69입니다. (즉, 자릿수의 합이 15인 3자리 숫자는 총 69개)

알고리즘 접근 방식

이 문제는 동적 계획법(DP)과 메모이제이션을 활용해 효율적으로 해결할 수 있습니다. 재귀적으로 각 자리에 올 수 있는 숫자(0~9)를 하나씩 선택하면서 남은 자릿수와 남은 합에 대한 부분 문제를 해결하고, 그 결과를 메모리 테이블에 저장해 중복 계산을 방지합니다.

count(digit, sum) 함수

입력: 남은 자릿수, 남은 목표 합

출력: 해당 조건을 만족하는 숫자의 개수

Begin
    if digit = 0, then
        return true when sum = 0

    if memTable[digit, sum] is not vacant, then
        return memTable[digit, sum]
    answer := 0

    for i := 0 to 9 do
        if sum – i >= 0, then
            answer := answer + count(digit – 1, sum - i)
    done

    return memTable[digit, sum] := answer
End

numberCount(digit, sum) 함수

입력: 전체 자릿수, 주어진 목표 값

출력: 조건을 만족하는 숫자의 총 개수

Begin
    define memTable and make all space vacant
    res := 0

    for i := 1 to 9, do
        if sum – i >= 0, then
            res := res + count(digit – 1, sum - i)
    done

    return result
End

핵심 포인트는 최상위 자리에는 0이 올 수 없기 때문에 numberCount 함수에서는 시작 숫자를 1부터 9까지로 제한한다는 것입니다. 반면 나머지 자리에는 0도 허용되므로 count 함수에서는 0부터 9까지 탐색합니다.

C++ 구현 예제

#include<iostream>
#define ROW 101
#define COL 501
using namespace std;

unsigned long long int memTable[ROW][COL];

unsigned long long int count(int digit, int sum) {
    if (digit == 0)   // 자릿수가 0이면 합이 0인지 확인
        return sum == 0;

    if (memTable[digit][sum] != -1)   // 이미 계산된 부분 문제라면 저장된 값 반환
        return memTable[digit][sum];

    unsigned long long int ans = 0;   // 처음에는 답을 0으로 초기화

    for (int i=0; i<10; i++)   // 각 숫자별로 경우의 수를 누적
        if (sum-i >= 0)
            ans += count(digit-1, sum-i);
    return memTable[digit][sum] = ans;
}

unsigned long long int numberCount(int digit, int sum) {
    for(int i = 0; i<ROW; i++)   // 메모이제이션 테이블을 -1로 초기화
        for(int j = 0; j<ROW; j++)
            memTable[i][j] = -1;
             
    unsigned long long int result = 0;
    for (int i = 1; i <= 9; i++)   // 첫 자리는 1~9만 가능
        if (sum-i >= 0)
            result += count(digit-1, sum-i);
    return result;
}

int main() {
    int digit, sum;
    cout << "Enter digit count: "; cin >> digit;
    cout << "Enter Sum: "; cin >> sum;
    cout << "Number of values: " << numberCount(digit, sum);
}

실행 결과

Enter digit count: 3
Enter Sum: 15
Number of values: 69

복잡도 분석

메모이제이션을 사용하면 상태의 개수는 최대 n × sum(100 × 500 = 50,000개)이며, 각 상태에서 최대 10번의 반복을 수행하므로 전체 시간 복잡도는 O(n × sum × 10)입니다. 완전 탐색으로는 감당할 수 없는 큰 입력에도 효율적으로 동작합니다.