C++로 주어진 수 N의 약수 중 가장 큰 '좋은 수' 찾기

문제 개요

이 문제에서는 하나의 수 N이 주어지며, 우리의 과제는 N의 약수(divisor) 중에서 가장 큰 '좋은 수(good number)'를 찾는 것입니다.

여기서 좋은 수(good number)란 모든 자릿수가 그보다 낮은 자릿수들, 즉 오른쪽에 있는 자릿수들의 합보다 큰 수를 의미합니다. 예를 들어 732는 좋은 수입니다. 7 > 3+2이고, 3 > 2이기 때문입니다.

예제로 문제 이해하기

입력 : N = 15
출력 : 15

설명 −

15의 약수 : 1, 3, 5, 15

해결 접근 방법

이 문제의 간단한 해결 방법은 먼저 N의 모든 약수를 구하는 것입니다. 그다음 그중에서 가장 큰 좋은 수를 찾으면 되는데, 이 값은 N의 모든 소인수(prime factor)들을 곱한 값으로 추출할 수 있습니다.

즉, N을 소인수분해하여 얻어진 서로 다른 소인수들을 모두 곱하면 원하는 결과를 효율적으로 얻을 수 있습니다. 이 방법은 모든 약수를 일일이 나열하고 각각이 좋은 수인지 검사하는 것보다 훨씬 빠르며, 시간 복잡도는 O(√N)입니다.

구현 예제

아래 프로그램은 위 솔루션의 동작 방식을 보여줍니다.

#include <bits/stdc++.h>
using namespace std;
int findLargestGoodNumber(int n){
    vector<int> primeFactors;
    int x = n;
    for (int i = 2; i * i <= n; i++) {
        if (x % i == 0) {
            primeFactors.push_back(i);
            while (x % i == 0) 
                x /= i;
        }
    }
    if (x > 1) 
        primeFactors.push_back(x);
    int goodNumber = 1;
    for (int i = 0; i < primeFactors.size(); i++)
        goodNumber = goodNumber * primeFactors[i];
    return goodNumber;
}
int main(){
    int n = 28;
    cout<<"The largest good Number in divisor of "<<n<<" is "<<findLargestGoodNumber(n); 
   return 0;
}

코드 설명

함수 findLargestGoodNumber()는 2부터 √n까지 반복하면서 n의 소인수를 차례대로 찾습니다. 각 소인수를 발견하면 벡터에 저장하고, 해당 인수가 더 이상 나누어지지 않을 때까지 x를 나누어 중복 계산을 방지합니다. 반복이 끝난 후 x가 1보다 크면 남은 값 자체가 소인수이므로 벡터에 추가합니다. 마지막으로 저장된 모든 소인수를 곱하여 결과를 반환합니다.

실행 결과

The largest good Number in divisor of 28 is 14

위 예제에서 28의 서로 다른 소인수는 2와 7이며, 이들의 곱인 14가 28의 약수 중에서 찾고자 하는 가장 큰 좋은 수가 됩니다.