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

이 문제에서는 하나의 숫자 N이 주어집니다. 우리의 과제는 최소공배수(LCM)가 N이 되는 서로 다른 숫자들의 최대 합을 구하는 프로그램을 C++로 작성하는 것입니다.

문제 설명

N의 모든 약수를 찾아야 하며, 서로 다른 약수들을 모두 더하여 최대 합을 계산합니다.

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

입력

N = 12

출력

28

설명

N의 서로 다른 약수는 1, 2, 3, 4, 6, 12입니다.
합 = 1 + 2 + 3 + 4 + 6 + 12 = 28

해결 접근 방식

가장 간단한 해결 방법은 N의 모든 약수를 찾은 후, 서로 다른 약수들을 모두 더하여 결과를 얻는 것입니다.

이를 위해 1부터 √N까지 반복하면서 현재 숫자가 N을 나누어떨어뜨리는지 확인합니다. 나누어떨어진다면 해당 숫자와 그 몫(N/i)을 함께 더하는데, 이때 두 값이 같은 경우(즉, i가 √N인 경우)에는 중복되지 않도록 한 번만 더합니다. 마지막으로 계산된 maxSum을 반환합니다.

이 알고리즘의 시간 복잡도는 O(√N)으로 효율적입니다.

예제 코드

아래 프로그램은 위에서 설명한 솔루션의 동작을 보여줍니다.

#include <iostream>
using namespace std;
int calcMaxSumForLCM(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 = 17;
    cout<<"LCM이 "<<N<<"이 되는 서로 다른 숫자들의 합은 "<<calcMaxSumForLCM(N);
    return 0;
}

출력

LCM이 17이 되는 서로 다른 숫자들의 합은 18

위 예제에서 N = 17은 소수이므로 약수는 1과 17뿐입니다. 따라서 합은 1 + 17 = 18이 됩니다.