C++로 합이 N이고 곱이 최대가 되는 N의 네 개 약수 찾기

개념

정수 N이 주어졌을 때, 다음 두 조건을 동시에 만족하는 N의 네 개 약수를 찾는 것이 이 문제의 목표입니다.

네 약수의 합이 N과 같아야 합니다.
네 약수의 곱이 가능한 한 최대가 되어야 합니다.

만약 이러한 네 개의 약수를 찾는 것이 불가능하다면 "Not possible"을 출력합니다.

곱을 최대화하기 위해서는 네 약수가 서로 같은 값을 가져도 된다는 점에 유의하세요.

입력

출력

모든 약수 -> 1 2 4 5 8 10 16 20 40 80
최대 곱 -> 160000

약수 20을 네 번 선택하면 20 + 20 + 20 + 20 = 80이 되며, 이때 곱(20 × 20 × 20 × 20 = 160000)이 최대가 됩니다.

풀이 방법

이 문제는 다음과 같은 단계별 알고리즘으로 해결할 수 있습니다.

먼저 1부터 N의 제곱근까지 순회하면서 i와 n/i가 N을 나누는지 확인하여 N의 모든 약수를 구하고 벡터(vector)에 저장합니다.
벡터를 오름차순으로 정렬한 뒤 모든 요소를 출력합니다.
세 개의 중첩 반복문을 사용하여 네 번째 수와 함께 곱을 최대로 만드는 세 개의 수를 탐색합니다.
네 번째 수는 N에서 앞의 세 수를 뺀 값이며, 이 값이 N의 약수인지 확인합니다.
더 큰 곱이 발견되면 기존의 최댓값을 갱신합니다.
조건을 만족하는 네 개의 약수를 찾으면 최종 곱을 출력합니다.

예제 코드

// 합이 N이고 곱이 최대인 N의 네 약수를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;

// 약수를 찾고 네 약수를 출력하는 함수
void findfactors2(int n1) {
    vector<int> vec2;
    // 모든 약수를 벡터에 저장
    for (int i = 1; i * i <= n1; i++) {
        if (n1 % i == 0) {
            vec2.push_back(i);
            vec2.push_back(n1 / i);
        }
    }
    // 벡터 정렬
    sort(vec2.begin(), vec2.end());
    // 모든 약수 출력
    cout << "All the factors are -> ";
    for (int i = 0; i < vec2.size(); i++)
        cout << vec2[i] << " ";
    cout << endl;
    // 어떤 수든 1로 나누어 떨어지므로 초기값 설정
    int maxProduct2 = 1;
    bool flag2 = 1;
    // 세 개의 중첩 반복문으로 세 약수를 탐색
    for (int i = 0; i < vec2.size(); i++) {
        for (int j = i; j < vec2.size(); j++) {
            for (int k = j; k < vec2.size(); k++) {
                // 네 번째 약수를 y에 저장
                int y = n1 - vec2[i] - vec2[j] - vec2[k];
                // 네 번째 값이 음수가 되면 탐색 종료
                if (y <= 0)
                    break;
                // 이전 값보다 더 나은 곱이면 갱신
                if (n1 % y == 0) {
                    flag2 = 0;
                    maxProduct2 = max(vec2[i] * vec2[j] * vec2[k] * y, maxProduct2);
                }
            }
        }
    }
    // 조건을 만족하는 수가 존재하면 곱 출력
    if (flag2 == 0)
        cout << "Product is -> " << maxProduct2 << endl;
    else
        cout << "Not possible" << endl;
}

// 드라이버 코드
int main() {
    int n1;
    n1 = 80;
    findfactors2(n1);
    return 0;
}

실행 결과

All the factors are -> 1 2 4 5 8 10 16 20 40 80
Product is -> 160000

시간 복잡도

약수를 구하는 과정은 O(√N)의 시간이 걸리며, 약수의 개수를 K라고 할 때 세 개의 중첩 반복문 탐색에는 O(K³)이 소요됩니다. 따라서 전체 시간 복잡도는 대략 O(√N + K³) 수준입니다. N이 매우 커지면 탐색 비용이 빠르게 증가하므로, 입력 범위에 따라 최적화 전략을 고려하는 것이 좋습니다.