C++에서 숫자의 네 인수 곱을 최대화하는 방법

이 문제의 목표는 주어진 수 N에 대해 네 개의 인수 A, B, C, D를 찾아 그 곱이 최대가 되도록 하는 것입니다. 단, 다음 조건을 만족해야 합니다.

네 인수의 합은 반드시 N과 같아야 합니다. 즉, N = A + B + C + D

예제로 이해하기

입력 − N = 10

출력 − 20

설명 − 10의 인수는 1, 2, 5, 10입니다. 이 중 5 × 2 × 2 × 1 = 20으로 곱이 최대가 되며, 동시에 5 + 2 + 2 + 1 = 10이라는 조건도 만족합니다.

입력 − N = 16

출력 − 256

설명 − 16의 인수는 1, 2, 4, 8, 16입니다. 이 중 4 × 4 × 4 × 4 = 256으로 곱이 최대가 되며, 4 + 4 + 4 + 4 = 16이라는 조건 역시 만족합니다.

알고리즘 접근 방식

주어진 수의 인수를 저장할 int형 배열 Factors[]를 선언하고, 배열에 채워진 요소의 개수를 추적할 변수 K = 0을 초기화합니다.
주어진 수의 모든 인수를 찾는 함수 FindFactors()를 작성합니다.
i = 1부터 i * i <= N까지 반복문을 실행합니다.
반복문 안에서 if (N % i == 0) 조건으로 i가 인수인지 확인합니다.
i가 인수라면 (N / i == i)인지 추가로 검사합니다. 참이라면 i만 배열에 삽입하고, 그렇지 않다면 N / i와 i 두 값을 모두 Factors[]에 삽입합니다.
인수들 중 네 개를 골라 만들 수 있는 최대 곱을 구하는 함수 Product()를 작성합니다.
int product = 0;과 size = K + 1;로 초기화합니다.
네 개의 중첩 반복문을 size까지 실행하여 모든 인수 조합을 탐색합니다.
반복문 안에서 int sum = Factors[i] + Factors[j] + Factors[k] + Factors[l];로 각 조합의 합을 계산합니다.
sum == N이라면 pro = Factors[i] * Factors[j] * Factors[k] * Factors[l];로 해당 조합의 곱을 계산합니다.
pro > product라면 product = pro;로 최댓값을 갱신합니다.
모든 탐색이 끝나면 product를 반환합니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
// 인수를 저장할 배열
int Factors[30];
int K = 0;
// 인수를 찾는 함수
int FindFactors(int N){
    // i가 sqrt(N)에 도달할 때까지 반복
    for (int i = 1; i * i <= N; i++){
        if (N % i == 0){
            /* 두 인수가 같다면 하나만 삽입 */
            if ((N / i) == i){
                Factors[K] = i;
                K++;
            }
            else{
                // 첫 번째 인수를 배열에 삽입
                Factors[K] = N / i;
                K++;
                // 두 번째 인수를 배열에 삽입
                Factors[K] = i;
                K++;
            }
        }
    }
}
// 최대 곱을 찾는 함수
int Product(int N){
    int product = 0;
    int size = K + 1;
    for (int i = 0; i < size; i++)
        for (int j = 0; j < size; j++)
            for (int k = 0; k < size; k++)
                for (int l = 0; l < size; l++){
                    // 각 인수 조합의 합 계산
                    int sum = Factors[i] + Factors[j] + Factors[k] + Factors[l];
                    // 합이 N과 같은지 확인
                    if (sum == N){
                        // 인수들의 곱 계산
                        int pro = Factors[i] * Factors[j] * Factors[k] * Factors[l];
                        // 더 큰 값이 발견되면 product 갱신
                        if (pro > product)
                            product = pro;
                    }
                }
    return product;
}
// 메인 함수
int main(){
    int N = 10;
    // N의 인수를 찾는 함수 호출
    FindFactors(N);
    // 최대 곱을 구하는 함수 호출
    cout << Product(N);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력을 얻을 수 있습니다.

Maximum Profit: 20