C++로 합이 N이 되는 네 개의 약수를 찾아 최대 곱 구하기

정수 N이 주어졌을 때, N의 모든 약수를 구한 후 다음 두 조건을 동시에 만족하는 네 개의 약수를 찾아 그 곱을 출력하는 것이 이 문제의 목표입니다.

• 선택한 네 약수의 합이 정확히 N과 같아야 합니다.
• 네 약수의 곱이 가능한 한 최대가 되어야 합니다.

예를 들어 N이 24라고 가정해 보겠습니다. 24의 모든 약수는 1, 2, 3, 4, 6, 8, 12, 24입니다. 이 중 약수 6을 네 번 선택하면 6 + 6 + 6 + 6 = 24가 되어 합 조건을 만족하고, 이때 곱은 6 × 6 × 6 × 6 = 1296으로 최대값이 됩니다.

접근 방법

이 문제를 해결하려면 먼저 1부터 N까지의 모든 약수를 구한 뒤, 아래 조건들을 순서대로 확인해야 합니다.

• N이 소수라면 네 개의 약수 조합을 만들 수 없으므로 답은 존재하지 않습니다.
• N이 4로 나누어떨어지는 경우, 답은 x⁴입니다. 여기서 x는 N을 4로 나눈 몫입니다. 산술-기하 평균 부등식에 의해 합이 고정되어 있을 때 네 수가 모두 같을 때 곱이 최대가 되기 때문입니다.
• 그 외의 경우에는 마지막에서 세 번째로 큰 약수를 두 번 사용하는 것이 유리합니다. 해당 약수를 하나로 고정한 채, 나머지 두 약수는 중첩 반복문을 통해 탐색하여 합과 곱 조건을 만족하는 최적의 조합을 찾습니다.

예제 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool isPrime(int n) {
    if (n <= 1)
        return false;
    if (n <= 3)
        return true;
    if (n % 2 == 0 || n % 3 == 0)
        return false;
    for (int i = 5; i * i <= n; i = i + 6)
        if (n % i == 0 || n % (i + 2) == 0)
            return false;
    return true;
}

void get_factors(int N, vector<int> fact_vectors[]) {
    for (int i = 2; i < N; i++) {
        for (int j = 1; j * j <= i; j++) {
            if (i % j == 0) {
                if (i / j == j)
                    fact_vectors[i].push_back(j);
                else {
                    fact_vectors[i].push_back(j);
                    fact_vectors[i].push_back(i / j);
                }
            }
        }
        sort(fact_vectors[i].begin(), fact_vectors[i].end());
    }
}

int getProduct(int n) {
    vector<int> v[n + 100];
    get_factors(n + 100, v);

    if (n % 4 == 0) {
        int x = n / 4;
        x *= x;
        return x * x;
    } else {
        if (isPrime(n))
            return -1;
        else {
            int ans = -1;
            if (v[n].size() > 2) {
                int fac = v[n][v[n].size() - 3];
                for (int i = v[n].size() - 1; i >= 0; i--) {
                    for (int j = v[n].size() - 1; j >= 0; j--) {
                        if ((fac * 2) + (v[n][j] + v[n][i]) == n)
                            ans = max(ans, fac * fac * v[n][j] * v[n][i]);
                    }
                }
                return ans;
            }
        }
    }
}

int main() {
    int n = 24;
    cout << "The product is: " << getProduct(n);
}

실행 결과

The product is: 1296

위 코드는 먼저 각 수의 약수를 벡터에 저장한 뒤, N이 4로 나누어떨어지는 경우 몫의 네제곱을 바로 반환합니다. 그렇지 않은 경우 소수 여부를 검사하고, 소수가 아니라면 세 번째로 큰 약수를 두 번 활용하는 전략으로 중첩 반복문을 돌며 최대 곱을 계산합니다. N이 24일 때 결과는 예상대로 1296이 출력됩니다.