두 개의 정수 N과 D가 주어집니다. N은 탐색 범위 [1, N]을 정의하고, D는 기준이 되는 차이값입니다. 이 문제의 목표는 범위 [1, N] 안에서 (수 − 그 수의 자릿수 합) > D 조건을 만족하는 모든 수를 찾아 그 개수를 구하는 것입니다.
해결 방법은 간단합니다. 1부터 N까지의 수를 하나씩 순회하면서, 각 수에 대해 while 루프로 자릿수 합을 계산한 뒤, 원래 수에서 자릿수 합을 뺀 값이 D보다 큰지 확인하면 됩니다.
예제로 이해하기
입력
N=15, D=5
출력
조건을 만족하는 수의 개수: 6
설명
10, 11, 12, 13, 14, 15가 조건을 만족합니다. (10−1, 11−2, 12−3, 13−4, 14−5, 15−6)의 차이는 모두 9로, 5보다 큽니다.
입력
N=20, D=10
출력
조건을 만족하는 수의 개수: 1
설명
20만 조건을 만족합니다. 20−2=18로, 10보다 큽니다.
접근 방법
- 정수 N과 D를 입력받습니다.
- 함수 digitSum(int n, int d)는 N과 D를 매개변수로 받아, (수 − 자릿수 합) > d를 만족하는 수의 개수를 반환합니다.
- 조건을 만족하는 수의 개수를 저장할 변수 count를 0으로 초기화합니다.
- 자릿수 합을 저장할 변수 digsum을 선언합니다.
- for 루프를 사용해 i = 1부터 i = n까지 수를 순회합니다.
- 각 수마다 num = i로 설정한 뒤, while 루프로 num이 0보다 큰 동안 반복합니다.
- digsum += num % 10으로 마지막 자릿수를 더하고, num = num / 10으로 다음 자릿수를 처리합니다.
- while 루프가 끝나면 (i − digsum > d) 조건을 검사하여 참이면 count를 증가시킵니다.
- 모든 반복이 끝나면 count에는 조건을 만족하는 수의 총 개수가 저장되며, 이 값을 결과로 반환합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int digitSum(int n, int d){
int count = 0;
int digsum = 0;
for (int i = 1; i <= n; i++){
int num = i;
digsum = 0;
while(num > 0){
digsum += num % 10; // 자릿수 합 계산
num = num / 10;
}
if(i - digsum > d){ // 원래 수는 i
count++;
//cout<<i<<" ";
}
}
return count;
}
int main(){
int N = 20;
int D = 8;
cout << "수와 자릿수 합의 차이가 특정 값보다 큰 수의 개수: " << digitSum(N, D);
return 0;
}출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
수와 자릿수 합의 차이가 특정 값보다 큰 수의 개수: 11
N=20, D=8인 경우, 10부터 19까지의 수는 모두 (수 − 자릿수 합) = 9 > 8을 만족하고, 20 역시 20−2=18 > 8을 만족하므로 총 11개의 수가 조건에 해당합니다.
복잡도 분석
시간 복잡도: O(N × log₁₀N) — 1부터 N까지 각 수에 대해 자릿수 길이만큼 반복하며 자릿수 합을 계산합니다.
공간 복잡도: O(1) — 추가적인 배열이나 자료구조 없이 상수 공간만 사용합니다.