정수 범위(start~end)와 나누는 수(m), 그리고 확인하고자 하는 숫자(d)가 주어졌을 때, 해당 범위 안에서 m으로 나누어떨어지면서 동시에 짝수 자릿수에 숫자 d를 포함하는 수의 개수를 계산하는 것이 이번 글의 목표입니다.
단순히 범위 전체를 하나씩 검사하는 방법도 가능하지만, 범위가 커지면 비효율적입니다. 따라서 이 글에서는 각 자릿수를 한 단계씩 결정해 나가는 디지트 DP(Digit DP) 기법과 메모이제이션을 활용해 효율적으로 문제를 해결합니다.
예제
예제 1
입력 - int start = 20, end = 50, d = 8, m = 4
출력 - 범위 내에서 m으로 나누어떨어지고 짝수 자릿수에 숫자 d를 가진 수의 개수: 2
설명 - 범위는 20부터 50까지입니다. 숫자 8을 포함하는 수는 28, 38, 48이며, 이 수들은 모두 두 번째(짝수) 자리에 8을 가지고 있습니다. 이 중 m인 4로 나누어떨어지는 수는 28과 48 두 개뿐이므로 최종 개수는 2가 됩니다.
예제 2
입력 - int start = 10, end = 100, d = 6, m = 2
출력 - 범위 내에서 m으로 나누어떨어지고 짝수 자릿수에 숫자 d를 가진 수의 개수: 8
설명 - 범위는 10부터 100까지입니다. 숫자 6을 포함하는 수는 16, 26, 36, 46, 56, 66, 76, 86, 96입니다. 이 중 66은 첫 번째(홀수) 자리에도 6이 있으므로 조건에서 제외됩니다. 남은 수들은 모두 짝수 자릿수에 6을 가지면서 m인 2로 나누어떨어지므로 최종 개수는 8이 됩니다.
프로그램에서 사용되는 접근 방식
- start부터 end까지의 정수 범위를 준비하고, 변수 d와 m을 선언해 값을 입력한 뒤 추가 처리를 위해 함수에 데이터를 전달합니다.
- 각 자릿수를 저장하기 위해 vector 타입의 변수(예: vec)를 생성합니다.
- val이 0이 될 때까지 while 반복문을 돌며 val % 10 값을 vec에 push하고, val을 val / 10으로 갱신해 자릿수를 하나씩 분리합니다.
- STL의 reverse 함수에 vec.begin()과 vec.end()를 인자로 전달해 호출하여 자릿수 배열을 왼쪽부터 읽는 순서로 뒤집습니다.
- memset을 사용해 메모이제이션 배열(arr)의 모든 값을 -1로 초기화합니다.
- set_total(0, 0, 0, vec)을 반환합니다. 이 함수는 짝수 자릿수에 d가 위치하면서 m으로 나누어떨어지는 수의 개수를 재귀적으로 계산합니다.
set_total 함수 내부 동작
- place가 vector의 크기와 같으면(모든 자릿수를 확정한 경우), temp가 0일 때 1을, 그렇지 않으면 0을 반환합니다. 즉, 지금까지 만든 수를 m으로 나눈 나머지가 0이면 유효한 수로 셉니다.
- arr[place][temp][val]이 -1이 아니면 이미 계산된 상태이므로 해당 값을 그대로 반환합니다(메모이제이션).
- place % 2가 1인 경우(짝수 번째 자리):
- val이 0일 때 d > vec[place]이면 더 이상 유효한 수를 만들 수 없으므로 0을 반환합니다.
- 변수 temp_2를 선언하고 val 값으로 초기화합니다.
- d < vec[place]이면 temp_2를 1로 설정합니다(현재 자리에서 이미 상한보다 작아짐).
- 변수 temp_3를 선언해 set_total(place + 1, (10 * temp + d) % m, temp_2, vec)을 재귀 호출한 결과를 저장한 뒤, arr[place][temp][val] = temp_3을 반환합니다. 짝수 자리에는 반드시 d가 놓입니다.
- 그 외의 경우(홀수 번째 자리):
- 결과를 누적할 변수 count를 선언합니다.
- 변수 set_limit를 선언하고, val이 1이면 9, 아니면 vec[place]로 설정합니다.
- i를 0부터 set_limit까지 반복하며, i가 d와 같으면 continue로 건너뜁니다(짝수 자리가 아닌 곳에는 d가 올 수 없음).
- 변수 temp_2를 val 값으로 설정하고, i < vec[place]이면 temp_2를 1로 설정합니다.
- count에 set_total(place + 1, (10 * temp + i) % m, temp_2, vec)의 재귀 호출 결과를 누적합니다.
- arr[place][temp][val] = count를 반환합니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
int arr[20][20][2];
int d, m;
int set_total(int place, int temp, int val, vector < int > vec) {
if (place == vec.size()) {
if (temp == 0) {
return 1;
}
return 0;
}
if (arr[place][temp][val] != -1) {
return arr[place][temp][val];
}
if (place % 2) {
if (val == 0) {
if (d > vec[place]) {
return 0;
}
}
int temp_2 = val;
if (d < vec[place]) {
temp_2 = 1;
}
int temp_3 = set_total(place + 1, (10 * temp + d) % m, temp_2, vec);
return arr[place][temp][val] = temp_3;
}
int count = 0;
int set_limit = (val ? 9 : vec[place]);
for (int i = 0; i <= set_limit; i++) {
if (i == d) {
continue;
}
int temp_2 = val;
if (i < vec[place]) {
temp_2 = 1;
}
count += set_total(place + 1, (10 * temp + i) % m, temp_2, vec);
}
return arr[place][temp][val] = count;
}
int divisible(int val) {
vector < int > vec;
while (val) {
vec.push_back(val % 10);
val = val / 10;
}
reverse(vec.begin(), vec.end());
memset(arr, -1, sizeof(arr));
return set_total(0, 0, 0, vec);
}
int main() {
int start = 20, end = 50;
d = 8, m = 4;
int count = divisible(end) - divisible(start);
cout << "Count of Numbers in a Range divisible by m and having digit d in even positions are: " << count;
return 0;
}위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
출력 결과
Count of Numbers in a Range divisible by m and having digit d in even positions are: 2
이 접근 방식은 상태 공간이 (자릿수 개수 × m × 2)로 제한되므로, 매우 큰 범위에서도 빠르게 답을 구할 수 있습니다. 또한 divisible(end) − divisible(start) 형태로 계산하면 시작 값 자체가 조건을 만족하는 경우도 정확하게 처리할 수 있습니다.