C++에서 LCM이 N인 서로 다른 숫자들의 최대 합 구하기

이 문제에서는 하나의 숫자 N이 주어지며, 최소공배수(LCM)가 N이 되는 서로 다른 숫자들의 최대 합을 구하는 C++ 프로그램을 작성해야 합니다.

문제 설명

주어진 숫자 N을 최소공배수(LCM)로 가지는 서로 다른 양의 정수들을 찾고, 이 숫자들의 합이 최대가 되도록 만들어야 합니다.

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

입력

N = 10

출력

18

설명

LCM이 10일 때의 최대 합은 1 + 2 + 5 + 10 = 18 입니다.

해결 접근 방법

이 문제의 핵심 아이디어는 다음과 같습니다. 어떤 수 집합의 최소공배수가 정확히 N이 되려면, 집합에 포함된 모든 숫자는 반드시 N의 약수여야 합니다. 최소공배수는 집합 내 모든 원소의 공통 배수이므로, 각 원소는 N을 나누어 떨어지게 하는 수, 즉 N의 약수일 수밖에 없습니다.

따라서 합을 최대화하려면 N의 모든 약수를 집합에 포함시키면 됩니다. N 자신도 약수에 포함되므로 전체 집합의 최소공배수는 반드시 N이 되고, 이때 얻어지는 합이 곧 최대 합(maxSum)입니다. 결국 정답은 N의 모든 약수의 합과 같습니다.

구현 예제

아래 프로그램은 위 해결 방법의 동작을 보여줍니다.

#include <iostream>
using namespace std;

int calcFactorSum(int N){
    int maxSum = 0;
    for (int i = 1; i*i <= N; i++){
        if (N % i == 0) {
            if (i == (N/i))
                maxSum = maxSum + i;
            else
                maxSum = maxSum + i + (N/i);
        }
    }
    return maxSum;
}
int main(){
    int N = 42;
    cout<<"The sum of distinct numbers with LCM as "<<N<<" is "<<calcFactorSum(N);
    return 0;
}

출력 결과

The sum of distinct numbers with LCM as 42 is 96

위 코드는 1부터 √N까지만 검사하여 약수 쌍(i와 N/i)을 동시에 찾는 방식으로 동작합니다. 덕분에 시간 복잡도 O(√N) 안에 N의 모든 약수의 합을 효율적으로 계산할 수 있습니다. 또한 i와 N/i가 같은 값이 되는 경우(즉, N이 완전제곱수인 경우)에는 같은 약수를 두 번 더하는 중복을 피하기 위해 조건문으로 한 번만 더하도록 처리했습니다.