C++에서 숫자와 자릿수 합의 차이가 L 이상인 수의 개수 구하기 (이진 탐색)

문제 개요

하나의 수 N과 또 다른 수 L이 주어집니다. 목표는 1부터 N 사이의 숫자 중에서 그 수 자신과 각 자릿수의 합 사이의 차이가 L보다 작지 않은(즉, L 이상인) 수의 개수를 구하는 것입니다.

예를 들어 N=23, L=10이라면 조건을 만족하는 수는 4개입니다.

23 − (2 + 3) = 18
22 − (2 + 2) = 18
21 − (2 + 1) = 18
20 − (2 + 0) = 18

위의 네 수는 모두 조건을 만족합니다. 반면 19 − (1 + 9) = 9로 L보다 작으므로 19, 18, 17, …, 1은 조건을 만족하지 않습니다.

입출력 예시

입력: N=30, L=19
출력: 1
설명: 30 − (3 + 0) = 27 > 19이므로 30만 조건을 만족합니다.
입력: N=123330, L=5466
출력: 6841

접근 방법: 이진 탐색(Binary Search)

핵심 아이디어는 이진 탐색을 이용해 조건을 처음으로 만족하는 수를 찾는 것입니다. 그 수를 num이라고 하면, num+1 이후의 모든 수도 같은 조건을 만족합니다. 수가 커질수록 '수 − 자릿수 합' 값도 단조롭게 증가하기 때문입니다(자릿수 합은 최대 9 × 자릿수에 불과합니다).

따라서 어떤 중간값(mid)이 조건을 만족한다면 mid부터 끝(end)까지의 모든 수도 조건을 만족하므로, (end − mid + 1)을 개수에 한 번에 더할 수 있습니다.

알고리즘 단계

num과 L을 long long형 변수로 받습니다.
Digit_sum(LL num) 함수는 수 num을 받아 자릿수의 합을 반환합니다. 초기 합을 total=0으로 두고, while 루프에서 num % 10을 total에 더한 뒤 num을 10으로 나누어 num > 0일 때까지 반복합니다.
Less_than_L(LL num, LL L) 함수는 조건을 만족하는 수의 개수를 반환합니다. 초기 count는 0으로 설정합니다.
start=1, end=num으로 설정하고 while 루프로 이진 탐색을 수행합니다.
중간값을 temp = (start + end) / 2로 계산합니다.
temp와 temp의 자릿수 합의 차이가 L 이상이면, temp보다 큰 모든 수도 조건을 만족합니다. temp를 포함한 개수(num − temp + 1)를 count에 더하고 end = temp − 1로 갱신합니다.
그렇지 않으면 start = temp + 1로 갱신합니다.
이진 탐색이 종료되면 count에는 조건을 만족하는 수의 개수가 저장되며, 이를 결과로 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

// 자릿수의 합을 구하는 함수
int Digit_sum(LL num){
    LL total = 0;
    while (num > 0){
        total += num % 10;
        num = num / 10;
    }
    return total;
}

// 조건을 만족하는 수의 개수를 구하는 함수
LL Less_than_L(LL num, LL L){
    LL count = 0;
    LL start = 1;
    LL end = num;
    while (start <= end){
        LL temp = (end + start) / 2;
        LL diff = temp - Digit_sum(temp);
        if (diff >= L){
            count = num - temp + 1;
            end = temp - 1;
        }
        else{
            start = temp + 1;
        }
    }
    return count;
}

int main(){
    LL num = 234516;
    LL L = 235;
    cout << "숫자와 자릿수 합의 차이가 L 이상인 수의 개수: " << Less_than_L(num, L);
    return 0;
}

실행 결과

숫자와 자릿수 합의 차이가 L 이상인 수의 개수: 234267

복잡도 분석

자릿수 합 계산에는 O(log N)의 시간이 걸리고, 이진 탐색 역시 O(log N)번 반복되므로 전체 시간 복잡도는 O((log N)²)입니다. 1부터 N까지 모든 수를 하나씩 검사하는 O(N log N) 방식보다 훨씬 효율적이며, N이 매우 큰 경우에도 빠르게 답을 구할 수 있습니다.