하나의 숫자를 담은 문자열 str과 원하는 자릿수 합 total이 입력으로 주어집니다. 이때 목표는 N(str) 이하의 숫자 중에서 각 자릿수의 합이 total과 정확히 일치하는 숫자가 몇 개 있는지 구하는 것입니다.
예제로 이해하기
입력 - N="110", sum=5
출력 - 자릿수 합이 5인 N 이하의 숫자 개수: 7
설명 - 110 이하에서 자릿수의 합이 5가 되는 숫자는 다음과 같습니다.
5, 14, 23, 32, 41, 50, 104
입력 - N="1000", sum=3
출력 - 자릿수 합이 3인 N 이하의 숫자 개수: 10
설명 - 1000 이하에서 자릿수의 합이 3이 되는 숫자는 다음과 같습니다.
3, 12, 21, 30, 102, 111, 120, 201, 210, 300
풀이 접근 방식
이 문제는 동적 계획법(Dynamic Programming)과 메모이제이션을 활용하면 효율적으로 해결할 수 있습니다. 숫자의 개수와 자릿수 합을 저장하기 위해 3차원 배열 arr[18][2][162]를 사용하며, 각 차원의 의미는 다음과 같습니다.
- 18 : 최대 18자리 숫자까지 처리할 수 있도록 하는 크기
- 2 : 0 또는 1 두 가지 상태를 저장 (현재까지 만든 숫자가 N의 접두사와 같은지, 이미 작아졌는지 여부)
- 162 : 가능한 최대 자릿수 합 (모든 자릿수가 9일 때 18 × 9 = 162)
배열 요소 arr[i][j][k]는 첫 i개의 자릿수를 고려한 숫자의 개수를 의미합니다. j는 현재 구성 중인 i자리 숫자가 N의 처음 i자리와 같은 상태인지, 아니면 이미 더 작은 상태인지를 나타내며, k는 해당 i개 자릿수의 합입니다. 예를 들어 N이 123이고 i가 2라면, 지금까지 만든 2자리 숫자가 12와 같은지(경계 상태) 아니면 이미 12보다 작은지(자유 상태)를 구분합니다.
재귀 호출이 문자열 끝(i = N의 자릿수)에 도달했을 때, 누적된 합 k가 입력으로 주어진 합과 같으면 1을 반환하고 그렇지 않으면 0을 반환합니다.
다음 자릿수(i+1번째)를 채울 때는 현재 상태를 확인합니다.
- 아직 N의 접두사와 같은 상태라면, 다음 자릿수는 N의 해당 자릿수 이하의 값만 사용할 수 있습니다. 그래야 최종 숫자가 N 이하로 유지됩니다.
- 이미 N의 접두사보다 작아진 상태라면, 다음 자릿수에는 0부터 9까지 어떤 값이 와도 됩니다.
모든 경우를 탐색한 뒤 최종 카운트를 결과로 반환합니다.
알고리즘 단계
- 숫자 N을 나타내는 문자열 str과 자릿수 합 total을 입력받습니다.
- 배열 arr[18][2][162]를 memset으로 -1로 초기화합니다.
- count_digits(int i, bool check, int temp, int total, string str, int size) 함수가 재귀적으로 arr[][][]를 채우고, 마지막에 조건을 만족하는 숫자의 개수를 반환합니다.
- 현재 자릿수 인덱스 i가 N의 길이와 같다면, 현재 합 temp가 total과 같을 때 1, 아니면 0을 반환합니다.
- count = arr[i][check][temp]를 확인하고, -1이 아니라면 이미 계산된 값이므로 그대로 반환합니다(메모이제이션).
- 임시 변수 check_2(bool)와 temp_2(int)를 준비합니다.
- for 루프로 문자 '0'부터 '9'까지 탐색하면서, 아직 경계 상태(check가 false)라면 현재 문자 ch가 str[i]보다 클 경우 반복을 중단합니다.
- check_2 = check || (ch < str[i])로 다음 상태를 갱신합니다. 한 번이라도 N보다 작은 자릿수를 놓으면 이후에는 자유롭게 선택할 수 있습니다.
- temp_2 = temp + (ch - '0')으로 현재까지의 자릿수 합을 갱신합니다.
- count += count_digits(i + 1, check_2, temp_2, total, str, size)로 재귀적으로 경우의 수를 누적합니다.
- 루프가 끝나면 count를 결과로 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int arr[18][2][162];
int count_digits(int i, bool check, int temp, int total, string str, int size) {
if (i == size) {
if (temp == total) {
return 1;
} else {
return 0;
}
}
int count = arr[i][check][temp];
if (count != -1) {
return count;
}
count = 0;
bool check_2;
int temp_2;
for (char ch = '0'; ch <= '9'; ch++) {
if (!check) {
if (ch > str[i]) {
break;
}
}
check_2 = check || ch < str[i];
temp_2 = temp + (ch - '0');
count += count_digits(i + 1, check_2, temp_2, total, str, size);
}
return count;
}
int main() {
string str = "1101";
int size = str.size();
int total = 5;
memset(arr, -1, sizeof(arr));
cout << "Count of numbers smaller than or equal to N with given digit sum are: " << count_digits(0, 0, 0, total, str, size);
return 0;
}
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
출력
Count of numbers smaller than or equal to N with given digit sum are: 26
이처럼 동적 계획법과 메모이제이션을 함께 사용하면, 1부터 N까지 모든 숫자를 하나씩 확인하는 브루트포스 방식보다 훨씬 빠르게 답을 구할 수 있습니다. 특히 N이 최대 18자리처럼 매우 큰 수일 때도 효율적으로 동작한다는 것이 이 접근법의 가장 큰 장점입니다.