자릿수(d)와 목표 합(sum)이 양의 정수로 주어졌을 때, 각 자릿수의 합이 입력된 합과 정확히 일치하는 모든 d자리 숫자의 개수를 구하는 것이 이 문제의 목표입니다. 단, 앞자리가 0으로 시작하는 숫자(선행 0)는 d자리 숫자로 인정하지 않습니다.
입력 범위는 자릿수가 1~100, 합은 1~500입니다.
예시를 통한 이해
예시 1
입력 - digits = 3, digi_sum = 3
출력 - 자릿수의 합이 주어진 합과 같은 n자리 숫자의 개수: 6
설명 - 자릿수의 합이 3인 세 자리 숫자는 다음과 같습니다.
102, 111, 120, 201, 210, 300
예시 2
입력 - digits = 4, digi_sum = 2
출력 - 자릿수의 합이 주어진 합과 같은 n자리 숫자의 개수: 4
설명 - 자릿수의 합이 2인 네 자리 숫자는 다음과 같습니다.
1001, 1010, 1100, 2000
프로그램에 적용한 접근 방식
이 방식에서는 가장 작은 d자리 숫자부터 탐색을 시작하여 자릿수의 합이 주어진 합과 일치하는 첫 번째 숫자를 찾습니다. 이후 자릿수의 합이 목표 합보다 커질 때까지 숫자를 9씩 증가시키며 탐색합니다. 자릿수의 합이 입력값보다 큰 숫자를 발견하면 1을 더한 뒤 다시 조건을 만족하는 다음 숫자를 찾습니다. 이 과정을 범위 내 마지막 d자리 숫자까지 반복합니다.
- 자릿수와 자릿수의 합을 입력받습니다.
- digits_sum(int digits, int digi_sum) 함수는 두 입력값을 받아 자릿수의 합이 주어진 합과 같은 n자리 숫자의 개수를 반환합니다.
- 초기 카운트(count)를 0으로 설정합니다.
- 탐색 범위의 시작 값을 Left = pow(10, digits - 1)로, 끝 값을 right = pow(10, digits) - 1로 지정합니다. (digits = 2라면 10부터 99까지)
- while 루프를 사용해 Left부터 right까지 순차적으로 탐색합니다.
- first = 0, last = i로 초기화합니다.
- 각 숫자 i(last)에 대해 가장 오른쪽 자릿수(last % 10)를 first에 더하고, last를 10으로 나누어 다음 반복을 준비합니다.
- first가 digi_sum과 같아지면 count를 1 증가시키고, i를 9만큼 늘려 다음 후보로 넘어갑니다.
- 조건이 맞지 않으면 i를 1 증가시킵니다.
- 모든 루프가 종료되면 count에는 자릿수의 합이 digi_sum과 같은 숫자들의 개수가 저장됩니다.
- count를 결과로 반환합니다.
구현 예제 코드
#include <bits/stdc++.h>
using namespace std;
int digits_sum(int digits, int digi_sum) {
int count = 0;
int Left = pow(10, digits - 1);
int right = pow(10, digits) - 1;
int i = Left;
while (i <= right) {
int first = 0;
int last = i;
while (last != 0) {
first = first + last % 10;
last = last / 10;
}
if (first == digi_sum) {
count++;
i = i + 9;
} else {
i++;
}
}
return count;
}
int main() {
int digits = 5;
int digi_sum = 7;
cout << "Count of n digit numbers whose sum of digits equals to given sum are: " << digits_sum(digits, digi_sum);
return 0;
}위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력 결과
Count of n digit numbers whose sum of digits equals to given sum are: 5
참고 사항
위 방식은 실제 숫자를 하나씩 확인하는 브루트 포스 기법으로, 입력 범위가 작을 때는 직관적이고 이해하기 쉽다는 장점이 있습니다. 하지만 자릿수가 커지면 탐색해야 할 숫자의 개수가 지수적으로 증가하므로 실행 시간이 급격히 늘어납니다. 따라서 입력 크기가 큰 경우에는 동적 계획법(DP)을 활용해 각 자릿수별로 가능한 합의 조합 수를 계산하는 방식이 훨씬 효율적입니다.