C++로 숫자의 인수 합 최솟값을 구하는 프로그램

이 프로그램은 주어진 수를 여러 인수의 곱으로 분해할 때, 인수들의 합이 최소가 되는 값을 찾습니다. 문제를 해결하는 기본 아이디어는 가능한 모든 인수 조합을 찾아 각각의 합을 계산하고, 그중에서 가장 작은 값을 선택하는 것입니다.

입력: n = 12
출력: 7

문제 설명

먼저 수 n의 인수들을 구한 뒤 이들을 더하여 합을 최소화해야 합니다. 12를 인수분해하는 다양한 방법과 각 경우의 인수 합은 다음과 같습니다.

12 = 12 × 1 → 12 + 1 = 13
12 = 2 × 6 → 2 + 6 = 8
12 = 3 × 4 → 3 + 4 = 7
12 = 2 × 2 × 3 → 2 + 2 + 3 = 7
따라서 최소 합은 7입니다.

핵심 아이디어

모든 조합을 일일이 비교하는 대신 소인수분해를 활용하면 효율적으로 답을 구할 수 있습니다. 합성수를 두 개 이상의 인수로 나눌 때, 소수 단위로 쪼갤수록 인수들의 합이 작아지는 성질이 있기 때문입니다. 예를 들어 6을 2와 3으로 나누면 2 + 3 = 5로, 6 자체보다 합이 작아집니다.

C++ 구현 예제

#include<iostream>
using namespace std;
int main() {
   int n = 12;
   int sum = 0;
   for (int i = 2; i * i <= n; i++) {
      while (n % i == 0) {
         sum += i;
         n /= i;
      }
   }
   sum += n;
   cout << sum;
   return 0;
}

코드 동작 원리

1. 2부터 √n까지의 수 중에서 n을 나누어 떨어지게 하는 가장 작은 인수를 찾습니다. 이 값은 항상 소수입니다.
2. 해당 인수로 더 이상 나누어지지 않을 때까지 나누면서, 그 인수를 결과 합에 더합니다.
3. 반복이 끝난 후 남은 n이 1보다 크다면 그 값 자체가 소수이므로 마지막 인수로 합에 더합니다.

이 알고리즘의 시간 복잡도는 O(√n)으로, 모든 인수 조합을 탐색하는 완전 탐색 방식보다 훨씬 효율적입니다.