Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 합이 N과 같고 곱이 최대가 되는 N의 4개 약수 찾기 - 세트 2

문제 개요

하나의 숫자 N이 주어졌을 때, N의 약수 가운데 네 개를 골라 다음 두 조건을 모두 만족하는 조합을 찾아야 합니다.

  • 네 약수의 합은 N과 같아야 합니다.
  • 네 약수의 곱은 가능한 한 커야(최대) 합니다.

곱을 극대화하기 위해 네 약수는 서로 동일한 값이어도 괜찮습니다.

예시

예를 들어 입력이 N = 60이라면 출력은 50625입니다. 60의 약수는 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60이며, 그중 15를 네 번 선택했을 때 곱이 가장 커집니다. 실제로 15 × 15 × 15 × 15 = 50625로, 합(15+15+15+15 = 60)과 최대 곱 조건을 동시에 충족합니다.

풀이 접근 방법

핵심 아이디어는 두 약수의 합을 하나의 "부분합"으로 묶어 관리하는 것입니다. 네 수 a, b, c, d의 합이 N이 되려면 (a + b) + (c + d) = N이 성립해야 하므로, 미리 계산해 둔 부분합들끼리 서로 보완 관계인지 확인하면 문제를 효율적으로 해결할 수 있습니다.

  1. my_map: 부분합의 존재 여부를 기록하는 맵을 준비합니다.
  2. v: N의 모든 약수를 담는 리스트, v1: 두 약수의 부분합을 담는 리스트를 생성합니다.
  3. i를 1부터 √n의 올림값까지 반복하면서 n mod i = 0인 경우 v에 i를 추가하고, i ≠ (n / i)이면서 i ≠ 1이면 n / i의 정수 부분도 함께 추가합니다.
  4. s := v의 크기로 설정하고, maximum := -1로 초기화합니다. 또한 크기 (n + 5)짜리 배열 map1을 0으로 채워 준비합니다.
  5. 모든 약수 쌍 (i, j)에 대해 v[i] + v[j] < n이면 그 합을 v1 끝에 추가하고, map1[v[i] + v[j]]에는 [v[i], v[j]] 쌍을, my_map에는 1을 기록합니다.
  6. s := v1의 크기로 갱신한 뒤, 각 부분합 v1[i]에 대해 element := n − v1[i]를 계산하고 element가 my_map에 존재하는지 확인합니다.
  7. 존재한다면 a, b는 map1[v1[i]]에서, c, d는 map1[n − v1[i]]에서 가져와 maximum과 a × b × c × d 중 더 큰 값을 maximum에 저장합니다.
  8. 마지막으로 maximum이 여전히 -1이면 "Not Possible"을 출력하고, 그렇지 않으면 maximum을 출력합니다.

약수의 개수를 m이라고 하면, 이중 루프 구조상 전체 시간 복잡도는 대략 O(m²)이며, map1 배열 사용으로 메모리 복잡도는 O(n) 수준입니다.

예제 코드

다음 구현을 통해 더 잘 이해할 수 있습니다.

from math import sqrt, ceil

def get_product(n):
    my_map = dict()
    v = []
    v1 = []
    for i in range(1, ceil(sqrt(n)) + 1):
        if n % i == 0:
            v.append(i)
            if i != (n // i) and i != 1:
                v.append(n // i)
    s = len(v)
    maximum = -1
    map1 = [0] * (n + 5)
    for i in range(s):
        for j in range(i, s):
            if v[i] + v[j] < n:
                v1.append(v[i] + v[j])
                map1[v[i] + v[j]] = [v[i], v[j]]
                my_map[v[i] + v[j]] = 1
    s = len(v1)
    for i in range(s):
        element = n - v1[i]
        if element in my_map:
            a = map1[v1[i]][0]
            b = map1[v1[i]][1]
            c = map1[n - v1[i]][0]
            d = map1[n - v1[i]][1]
            maximum = max(a * b * c * d, maximum)
    if maximum == -1:
        print("Not Possible")
    else:
        print("Maximum product", maximum)

n = 60
get_product(n)

입력

60

출력

Maximum product 50625

정리

이 방법은 약수를 먼저 구한 뒤, 두 약수씩 짝지은 부분합을 사전에 저장해 두고 나머지 두 수의 조합과 매칭하는 방식으로 동작합니다. 덕분에 네 약수를 일일이 탐색하는 완전 탐색보다 효율적으로 최대 곱을 찾을 수 있으며, 조건을 만족하는 조합이 없을 경우 "Not Possible"을 반환해 예외 상황도 깔끔하게 처리합니다.