파이썬(Python)으로 숫자 인수의 최소 합 구하기

이 글에서는 하나의 숫자가 주어졌을 때, 그 숫자를 구성하는 인수들의 합이 최소가 되는 값을 찾는 방법을 알아봅니다.

문제 정의

입력으로 하나의 숫자가 주어지면, 해당 숫자의 인수들을 이용해 만들 수 있는 합 중에서 가장 작은 값을 구해야 합니다.

모든 인수 조합을 일일이 계산해 각각의 합을 비교하는 방법도 있지만, 훨씬 효율적인 접근 방식이 존재합니다.

핵심 아이디어

곱이 주어진 숫자가 되도록 하는 여러 수들의 합을 최소화하려면, 그 숫자를 소인수분해하여 소인수들의 합을 구하면 됩니다.

예를 들어 12는 12, 6×2, 4×3, 3×2×2 등으로 표현할 수 있으며, 각 경우의 합은 12, 8, 7, 7입니다. 합성수를 더 작은 인수로 쪼갤수록 곱은 같지만 합은 줄어들기 때문에, 소인수까지 분해한 3+2+2=7이 최솟값이 됩니다.

반복문 기반 구현 예제

# 반복적 접근 방식
def findMinSum(num):
    sum_ = 0
    # 숫자의 인수를 찾아 합에 더함
    i = 2
    while(i * i <= num):
        while(num % i == 0):
            sum_ += i
            num //= i
        i += 1
    sum_ += num
    return sum_

# 드라이버 코드
num = 12
print(findMinSum(num))

출력 결과

7

동작 원리

위 코드는 다음과 같은 순서로 동작합니다.

1. 2부터 시작해 i * i <= num을 만족하는 동안 반복하면서, num이 i로 나누어떨어질 때마다 i를 합에 더하고 num을 i로 나눕니다.
2. 내부 반복이 끝나면 i를 1 증가시켜 다음 인수를 검사합니다.
3. 외부 반복이 종료된 후 남아 있는 num(소수 또는 1)을 마지막으로 합에 더해 반환합니다.

예를 들어 입력값이 12일 때, 2로 두 번 나누어 합이 4가 되고 남은 값 3을 더해 최종적으로 7이 출력됩니다. 제곱근까지만 검사하기 때문에 시간 복잡도는 O(√n)으로 매우 효율적입니다.

결론

이 글에서는 소인수분해를 활용해 주어진 숫자의 인수 합을 최소화하는 파이썬 구현 방법을 살펴보았습니다. 단순히 모든 조합을 탐색하는 대신 소인수의 성질을 이용하면 적은 연산으로 정답을 구할 수 있다는 점이 핵심입니다.