C++로 N보다 작으면서 자릿수 합이 더 큰 가장 큰 수 찾기

이 튜토리얼에서는 주어진 수 N의 자릿수 합보다 자릿수 합이 더 크면서, N보다 작은 수 중에서 가장 큰 수를 찾는 프로그램을 C++로 작성해 보겠습니다.

예를 들어 N이 75라면, 75의 자릿수 합은 7 + 5 = 12입니다. 이보다 작은 수 중 자릿수 합이 12보다 큰 가장 큰 수는 무엇일까요? 정답은 69로, 자릿수 합이 6 + 9 = 15이기 때문입니다.

문제 해결 접근 방법

문제를 해결하기 위한 절차는 다음과 같습니다.

• 숫자의 자릿수 합을 계산하는 함수를 작성합니다.
• N 값을 초기화합니다.
• n - 1부터 1까지 반복하는 루프를 작성합니다.
  • 현재 숫자의 자릿수 합과 n의 자릿수 합을 비교합니다.
  • 현재 숫자의 자릿수 합이 더 크면 해당 숫자를 반환합니다.
  • 조건을 만족하지 않으면 다음 숫자로 이동합니다.

예제 코드

위 알고리즘을 구현한 전체 코드를 살펴보겠습니다.

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

int sumOfDigits(int n) {
    int digitsSum = 0;
    while (n > 0) {
        digitsSum += n % 10;
        n /= 10;
    }
    return digitsSum;
}

int findLargestNumber(int n) {
    int i = n - 1;
    while (i > 0) {
        if (sumOfDigits(i) > sumOfDigits(n)) {
            return i;
        }
        i--;
    }
    return -1;
}

int main() {
    int n = 75;
    cout << findLargestNumber(n) << endl;
    return 0;
}

코드의 핵심 로직은 간단합니다. sumOfDigits 함수는 나눗셈과 나머지 연산을 반복하며 각 자릿수의 합을 구하고, findLargestNumber 함수는 n - 1부터 시작해 조건을 만족하는 첫 번째 수를 발견하는 즉시 반환합니다. 내림차순으로 탐색하기 때문에 조건을 처음 만족하는 수가 곧 가장 큰 수가 됩니다.

실행 결과

위 코드를 실행하면 다음과 같은 결과가 출력됩니다.

69

75보다 작은 수 중에서 자릿수 합(15)이 12보다 큰 가장 큰 수는 69임을 확인할 수 있습니다.

마무리

이처럼 자릿수 합 계산과 단순한 역방향 탐색만으로도 문제를 쉽게 해결할 수 있습니다. 참고로 N의 범위가 매우 큰 경우에는 완전 탐색 대신 수학적 성질을 활용한 최적화 기법을 고려할 수 있습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요.