C++로 정수 n의 모든 약수 중 가장 큰 자릿수 합 구하기

이 문제에서는 하나의 정수 n이 주어지며, n의 모든 약수 중에서 자릿수의 합이 가장 큰 값을 찾는 것이 목표입니다.

문제 설명

숫자 n의 모든 약수를 구한 뒤, 각 약수의 자릿수 합을 계산하고 그중 가장 큰 값을 결과로 반환하면 됩니다.

예제를 통해 문제를 이해해 보겠습니다.

입력: 18

출력: 9

설명:

18의 모든 약수는 1, 2, 3, 6, 9, 18입니다.
각 약수의 자릿수 합은 순서대로 1, 2, 3, 6, 9, 9이며, 이 중 최댓값은 9입니다.

기본 해결 접근 방법

가장 단순한 방법은 다음과 같습니다.

1. 1부터 n까지 모든 수를 확인하며 n의 약수를 찾습니다.
2. 각 약수에 대해 자릿수의 합을 계산합니다.
3. 자릿수 합이 가장 큰 값을 반환합니다.

자릿수의 합은 수를 10으로 나눈 나머지를 계속 더하고, 몫을 대입하며 반복하는 방식으로 손쉽게 구할 수 있습니다.

구현 예제

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
    
    int sum = 0;
    while (n != 0) {
        sum = sum + n % 10;
        n = n/10;
    }
    return sum;
}

int largestDigitSumdivisior(int n) {
    
    int maxSum = 0;
    for (int i = 1; i <= n; i++)
        if (n % i == 0)
        maxSum = max(maxSum, calcDigitSum(i));

    return maxSum;
}

int main() {
    
    int n = 45;
    cout<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
    return 0;
}

출력

The divisor with largest sum of digits is 9

이 방법의 시간 복잡도는 O(n)으로, n이 커질수록 비효율적입니다. 따라서 약수를 찾는 과정을 최적화하여 성능을 개선할 필요가 있습니다.

최적화된 해결 접근 방법

약수는 √n을 기준으로 대칭을 이룬다는 성질을 활용하면 효율성을 크게 높일 수 있습니다.

1부터 √n까지만 반복하면서 i가 n의 약수인 경우, 짝이 되는 약수인 n/i도 함께 처리합니다. 이렇게 하면 약수를 찾는 시간 복잡도가 O(√n)으로 줄어들어 실행 속도가 크게 향상됩니다.

구현 예제

#include <iostream>
using namespace std;

int calcDigitSum(int n) {
    
    int sum = 0;
    while (n != 0) {
        sum = sum + n % 10;
        n = n / 10;
    }
    return sum;
}

int largestDigitSumdivisior(int n) {
    
    int maxSum = 0;
    for (int i = 1; i*i <= n; i++) {

        if (n % i == 0) {
            maxSum = max(maxSum, calcDigitSum(i));
            maxSum = max(maxSum,calcDigitSum(n/i));
        }  
    }
    return maxSum;
}

int main() {
    
    int n = 32;
    cout<<"The divisor with largest sum of digits is "<<largestDigitSumdivisior(n)<<endl;
    return 0;
}

출력

The divisor with largest sum of digits is 8

마무리

32의 약수는 1, 2, 4, 8, 16, 32이며, 자릿수 합은 각각 1, 2, 4, 8, 7, 5입니다. 따라서 최댓값인 8이 출력됩니다.

이처럼 √n까지만 탐색하면서 짝 약수를 동시에 처리하면, 동일한 결과를 훨씬 빠른 시간 안에 얻을 수 있습니다. 입력 값이 큰 경우에도 효율적으로 동작하므로 실전 코딩 테스트에서도 유용하게 활용할 수 있는 기법입니다.