두 개의 숫자 START와 END가 주어져 하나의 숫자 범위를 정의합니다. 이 문제의 목표는 해당 범위 [START, END] 안에서 각 자릿수의 합이 주어진 값 Y와 같은 숫자가 모두 몇 개인지 찾는 것입니다.
해결 방법은 간단합니다. START부터 END까지 숫자를 하나씩 순회하면서, 각 숫자에 대해 while 루프를 이용해 자릿수의 합을 계산하고, 그 합이 Y와 같다면 카운트를 1씩 증가시키면 됩니다.
예제로 이해하기
입력 예시 1
START=10 END=20 Y=4
출력 결과 1
자릿수의 합이 Y와 같은 숫자의 개수: 1
설명
숫자 13은 1 + 3 = 4이므로 자릿수의 합이 4입니다.
입력 예시 2
START=10 END=50 Y=5
출력 결과 2
자릿수의 합이 Y와 같은 숫자의 개수: 5
설명
14, 23, 32, 41, 50의 다섯 개 숫자는 모두 자릿수의 합이 5입니다.
알고리즘 접근 방식
- 정수 START, END, Y를 입력받습니다.
- 함수 digitSum(int start, int end, int y)는 자릿수의 합이 y와 같은 숫자의 개수를 반환합니다.
- 조건을 만족하는 숫자를 세기 위한 변수 count를 0으로 초기화합니다.
- 자릿수의 합을 저장할 변수 digsum을 선언합니다.
- for 루프를 사용해 i = start부터 i = end까지 범위의 숫자를 순회합니다.
- 각 숫자에 대해 num = i로 설정한 뒤, while 루프로 num > 0인 동안 반복합니다.
- digsum += num % 10으로 마지막 자릿수를 더하고, num = num / 10으로 다음 자릿수를 준비합니다.
- while 루프가 끝나면 digsum == y인지 확인하고, 참이라면 count를 증가시킵니다.
- 모든 루프가 종료되면 count에는 조건을 만족하는 숫자의 총 개수가 저장됩니다.
- count를 결과값으로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int digitSum(int start, int end, int y){
int count = 0;
int digsum = 0;
for (int i = start; i <= end; i++){
int num=i;
digsum=0;
while(num>0){
digsum+=num%10; //sum of digits
num=num/10;
}
if(digsum==y) //original number is i{
count++;
//cout<<i<<" ";
}
}
return count;
}
int main(){
int START = 100;
int END = 1000;
int Y = 5;
cout <<"Numbers such that digit sum is equal to Y: "<<digitSum(START,END,Y);
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Numbers such that digit sum is equal to Y: 15
즉, 100부터 1000 사이에는 자릿수의 합이 5인 숫자가 총 15개 존재합니다. 이 알고리즘의 시간 복잡도는 O(N × D)입니다. 여기서 N은 범위 내 숫자의 개수, D는 각 숫자의 최대 자릿수를 의미하므로, 범위가 크지 않은 경우에 효율적으로 동작합니다.