문제 소개
두 개의 숫자 START와 END가 주어져 하나의 숫자 범위를 정의합니다. 이 문제의 목표는 [START, END] 범위 내에서 다음 세 가지 조건을 모두 만족하는 숫자의 개수를 찾는 것입니다.
- 숫자에 0인 자릿수가 하나도 없어야 합니다.
- 모든 자릿수의 합이 주어진 값 N과 같아야 합니다.
- 해당 숫자는 M으로 나누어떨어져야 합니다.
이를 해결하기 위해 START부터 END까지의 숫자를 순회하면서, 각 숫자에 대해 while 루프를 사용해 자릿수의 합을 계산합니다(단, 모든 자릿수가 0이 아닌 경우에만). 계산된 자릿수 합이 N과 같고, 그 숫자가 M으로 나누어떨어지면 카운트를 증가시킵니다.
구체적인 예시를 통해 이해해 보겠습니다.
예제 1
입력
START=1 END=100 N=9 M=6
출력
자릿수 합이 N이고 M으로 나누어떨어지는 숫자의 개수: 4
설명
18, 36, 54, 72는 각각 자릿수의 합이 9이고 6으로 나누어떨어집니다. 또한 네 숫자 모두 0을 자릿수로 포함하지 않습니다.
예제 2
입력
START=100 END=200 N=10 M=2
출력
자릿수 합이 N이고 M으로 나누어떨어지는 숫자의 개수: 4
설명
118, 136, 154, 172는 각각 자릿수의 합이 10이고 2로 나누어떨어집니다. 역시 0을 자릿수로 포함하지 않습니다.
접근 방법
아래 프로그램에서 사용한 접근 방식은 다음과 같습니다.
- 정수 START, END, N, M을 입력받습니다.
- digitSum(int start, int end, int n, int m) 함수는 자릿수 합이 n이고 m으로 나누어떨어지며, 모든 자릿수가 0이 아닌 숫자의 개수를 반환합니다.
- 조건을 만족하는 숫자를 세기 위한 초기 변수 count를 0으로 설정합니다.
- 자릿수의 합을 저장할 변수 digsum을 0으로 초기화합니다.
- 플래그 변수 flag를 0으로 초기화합니다.
- for 루프를 사용해 i=start부터 i=end까지 범위의 숫자를 순회합니다.
- 각 숫자 num=i에 대해 num%m==0(즉, m으로 나누어떨어지는 경우)일 때만 다음 단계로 진행합니다.
- while 루프로 num이 0보다 큰 동안 자릿수를 추출합니다.
- digit=num%10으로 자릿수를 구하고, 해당 자릿수가 0이 아니면 digsum+=digit으로 합산합니다. 이후 num=num/10으로 다음 자릿수를 준비합니다. 만약 자릿수 중 하나라도 0이면 flag=0으로 설정하고 while 루프를 종료합니다.
- while 루프가 끝난 후 digsum==n && flag==1인지 확인하고, 참이면 count를 증가시킵니다.
- 이후 i를 m의 배수만큼 증가시켜 불필요한 검사를 건너뜁니다(m으로 나누어떨어지는 수만 검사하면 되기 때문입니다).
- 모든 루프가 종료되면 count에는 조건을 만족하는 숫자의 총 개수가 저장됩니다.
- count를 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int digitSum(int start, int end, int n, int m){
int count = 0;
int digsum = 0;
int flag=0;
for (int i = start; i <= end; i++){
int num=i;
digsum=0;
flag=0;
if(num%m==0){
while(num>0){
int digit=num%10;
if(digit==0){
flag=0;
break;
}
digsum+=num%10; // 자릿수의 합
num=num/10;
flag=1;
}
if(digsum==n && flag==1){ // 원래 숫자는 i
count++;
cout<<i<<" ";
}
i+=m; // m의 배수만큼 증가
i--; // for 루프의 i++ 상쇄용
}
}
return count;
}
int main(){
int START = 1;
int END = 100;
int N = 9;
int M = 6;
cout <<"자릿수 합이 N이고 M으로 나누어떨어지는 숫자의 개수: "<<digitSum(START,END,N, M);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
자릿수 합이 N이고 M으로 나누어떨어지는 숫자의 개수: 4
마무리
이 알고리즘은 범위 내에서 M의 배수만 검사 대상으로 삼아 연산 횟수를 줄이고, 자릿수 중 0이 발견되면 즉시 루프를 탈출하는 방식으로 효율성을 높였습니다. 시간 복잡도는 대략 O((END - START) / M × log(END)) 수준으로, 범위가 넓어질 때도 실용적인 성능을 보여줍니다. 더 큰 범위나 여러 쿼리를 처리해야 하는 경우에는 자릿수 DP(Digit DP) 기법을 활용하면 훨씬 빠르게 해결할 수 있습니다.