합이 N과 같고 곱이 최대가 되는 N의 네 개 약수 찾기

개념

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

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

만약 조건을 만족하는 네 개의 약수를 찾을 수 없다면 "Not possible"을 출력합니다. 흥미로운 점은 곱을 최대화하기 위해 네 약수가 모두 같은 값이어도 된다는 것입니다.

입력

N = 60

출력

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60
Product is -> 50625

위 예제에서는 약수 15를 네 번 선택했습니다. 15 + 15 + 15 + 15 = 60이라는 합 조건을 만족하면서, 15 × 15 × 15 × 15 = 50625로 네 약수의 곱이 가장 크게 되기 때문입니다.

접근 방법

P를 N의 약수 개수라고 할 때, 세 개의 중첩 반복문을 사용하는 단순한 방법은 O(P³)의 시간 복잡도를 가집니다. 반면 다음 단계를 활용하면 시간 복잡도를 O(N²) 수준까지 줄일 수 있습니다.

주어진 수의 모든 약수를 하나의 컨테이너(벡터)에 저장합니다.
가능한 모든 쌍(pair)을 순회하면서 각 쌍의 합을 별도의 컨테이너에 저장합니다.
나중에 합을 만든 원소를 추적할 수 있도록 인덱스(element1 + element2) 위치에 쌍(element1, element2)을 기록합니다.
저장된 모든 쌍의 합을 다시 순회하면서 n − pair_sum이 같은 컨테이너에 존재하는지 확인합니다. 존재한다면 두 쌍이 합쳐져 조건을 만족하는 네 개의 약수 조합을 형성합니다.
쌍 해시 배열을 사용해 해당 합이 어떤 원소들로 만들어졌는지 역추적합니다.
마지막으로 가능한 조합 중 곱이 가장 큰 값을 저장해 두었다가 최종적으로 출력합니다.

예제 코드

// 합이 N과 같으면서 곱이 최대가 되는
// N의 네 개 약수를 찾는 C++ 프로그램
#include <bits/stdc++.h>
using namespace std;

// 약수를 구하고 네 개의 약수와 곱을 출력하는 함수
void findfactors1(int q){
    vector<int> vec1;
    // 모든 약수를 벡터에 삽입
    for (int i = 1; i * i <= q; i++) {
        if (q % i == 0) {
            vec1.push_back(i);
            vec1.push_back(q / i);
        }
    }
    // 벡터를 오름차순으로 정렬
    sort(vec1.begin(), vec1.end());
    // 모든 약수 출력
    cout << "All the factors are -> ";
    for (int i = 0; i < vec1.size(); i++)
        cout << vec1[i] << " ";
    cout << endl;

    int maxProduct1 = 1;   // 최대 곱 초기화 (모든 수는 1로 나누어떨어짐)
    bool flag1 = true;     // 가능한 조합 여부 플래그

    // 세 개의 중첩 반복문으로 세 개의 약수를 선택
    for (int i = 0; i < vec1.size(); i++) {
        for (int j = i; j < vec1.size(); j++) {
            for (int k = j; k < vec1.size(); k++) {
                // 네 번째 약수를 y로 계산
                int y = q - vec1[i] - vec1[j] - vec1[k];
                // 네 번째 값이 0 이하가 되면 탐색 종료
                if (y <= 0)
                    break;
                // y가 N의 약수라면 더 나은 결과로 갱신
                if (q % y == 0) {
                    flag1 = false;
                    maxProduct1 = max(vec1[i] * vec1[j] * vec1[k] * y, maxProduct1);
                }
            }
        }
    }
    // 조건을 만족하는 조합이 있으면 곱 출력
    if (!flag1)
        cout << "Product is -> " << maxProduct1 << endl;
    else
        cout << "Not possible" << endl;
}

// 드라이버 코드
int main(){
    int q;
    q = 60;
    findfactors1(q);
    return 0;
}

출력 결과

All the factors are -> 1 2 3 4 5 6 10 12 15 20 30 60
Product is -> 50625

코드 설명

약수 수집: findfactors1 함수는 1부터 √q까지 순회하며 나누어떨어지는 값 i와 그 짝인 q/i를 함께 벡터에 저장한 뒤 오름차순으로 정렬합니다.
세 약수 선택: 세 개의 중첩 반복문으로 세 개의 약수를 고르고, 네 번째 값 y는 q에서 세 약수의 합을 뺀 값으로 계산됩니다.
가지치기: y가 0 이하가 되면 더 큰 조합은 탐색할 필요가 없으므로 즉시 반복을 종료(break)합니다.
최댓값 갱신: y가 N의 약수인 경우에만 네 수의 곱을 계산하여 기존 최댓값보다 크면 갱신합니다.
결과 출력: 조건을 만족하는 조합이 하나라도 존재하면 최대 곱을, 존재하지 않으면 "Not possible"을 출력합니다.

합이 N과 같고 곱이 최대가 되는 N의 네 개 약수 찾기 - C++ Set-2

개념

입력

출력

접근 방법

예제 코드

출력 결과

코드 설명