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

숫자 N이 주어졌을 때, N의 모든 약수를 구한 뒤 다음 조건을 만족하는 네 개의 약수를 찾아 그 곱을 반환해야 합니다.

네 약수의 합은 정확히 N과 같아야 합니다.
네 약수의 곱은 가능한 한 최대가 되어야 합니다.
곱을 극대화하기 위해 네 약수가 서로 같은 값이어도 괜찮습니다.

문제 예시

예를 들어 N = 60이라고 가정해 보겠습니다. 이 경우 60의 모든 약수는 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60이며, 그중 15를 네 번 선택했을 때 곱이 15 × 15 × 15 × 15 = 50625로 최대가 됩니다. 물론 15 × 4 = 60이므로 합 조건도 만족합니다.

해결 접근 방법

이 문제는 다음 단계를 통해 해결할 수 있습니다.

빈 리스트 factors를 생성합니다.
1부터 √n까지(정수 부분 + 1) 반복하면서, n을 i로 나누어 떨어지면 i와 n // i를 약수 리스트에 추가합니다. 이 방법으로 O(√n) 시간에 모든 약수를 구할 수 있습니다.
약수 리스트를 오름차순으로 정렬하고 출력합니다.
final_prod := 1, flag := 1로 초기화합니다.
세 겹의 반복문(i ≤ j ≤ k)을 사용해 세 개의 약수를 선택하고, 나머지 하나인 y = n − factors[i] − factors[j] − factors[k]를 계산합니다.
y가 0 이하면 더 이상 진행할 수 없으므로 내부 반복문을 종료합니다.
y가 n의 약수(n mod y == 0)라면 flag를 0으로 설정하고, 현재 네 수의 곱과 final_prod 중 큰 값을 final_prod에 저장합니다.
반복이 끝난 후 flag가 0이면(유효한 조합이 존재하면) final_prod를 출력하고, 그렇지 않으면 "Not possible"을 출력합니다.

Python 구현 예제

다음 코드를 통해 동작 방식을 더 잘 이해할 수 있습니다.

from math import *

def get_factors(n):
    factors = []
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            factors.append(i)
            factors.append(n // i)
    factors.sort()
    print("Factors are", factors)

    final_prod = 1
    flag = 1
    for i in range(len(factors)):
        for j in range(i, len(factors)):
            for k in range(j, len(factors)):
                y = n - factors[i] - factors[j] - factors[k]
                if y <= 0:
                    break
                if n % y == 0:
                    flag = 0
                    final_prod = max(factors[i] * factors[j] * factors[k] * y, final_prod)
    if flag == 0:
        print("Product is", final_prod)
    else:
        print("Not possible")

n = 60
get_factors(n)

입력

출력

Factors are [1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60]
Product is 50625

복잡도 분석

약수를 구하는 과정은 O(√N)이지만, 세 겹의 반복문으로 세 약수의 조합을 탐색하므로 전체 시간 복잡도는 약수 개수를 D라고 할 때 O(D³)입니다. 따라서 이 방법은 N이 크지 않은 경우에 적합하며, N이 매우 큰 경우에는 수학적 최적화(예: 곱이 최대가 되려면 네 수가 N/4에 가까워야 한다는 성질 활용)를 고려하는 것이 좋습니다.