이 문제에서는 정수 N이 주어집니다. 우리의 과제는 N을 약수(제수)로 반복해서 나눈 후 얻을 수 있는 최대 합을 찾는 프로그램을 C++로 작성하는 것입니다.
문제 설명
숫자 N을 1이 될 때까지 재귀적으로 계속 나누고, 그 과정에서 등장하는 모든 값(N 자신 포함)을 더했을 때 만들어질 수 있는 최대 합을 구합니다.
예를 들어 문제를 이해해 보겠습니다.
입력 − N = 12
출력 − 22
설명 − 숫자를 반복해서 나누고 그 합을 구해 보면 다음과 같습니다.
나눗셈 1: 12 / 2 = 6
나눗셈 2: 6 / 2 = 3
나눗셈 3: 3 / 3 = 1
합계 = 12 + 6 + 3 + 1 = 22
접근 방법
이 문제를 해결하는 핵심 아이디어는 간단합니다. 어떤 수를 나눌 때 가장 작은 약수로 나누면 몫이 가장 커지기 때문에, 매 단계마다 현재 수의 최소 약수로 나누는 것이 항상 최대 합을 보장합니다.
즉, 각 단계에서:
- 현재 수 n의 가장 작은 약수를 찾습니다.
- n을 그 약수로 나눈 몫으로 갱신합니다.
- 갱신된 값을 누적 합에 더합니다.
이 과정을 n이 1이 될 때까지 반복하면 됩니다.
예제 코드
아래는 위 해결 방법의 동작을 보여주는 프로그램입니다.
#include <bits/stdc++.h>
using namespace std;
// 가장 작은 약수를 찾는 함수
int smallestDivisor(int n){
int mx = sqrt(n);
for (int i = 2; i <= mx; i++)
if (n % i == 0)
return i;
return n; // 소수인 경우 자기 자신 반환
}
// 최대 합을 계산하는 함수
int calculateMaxSum(int n) {
long long maxSum = n;
while (n > 1) {
int divisor = smallestDivisor(n);
n /= divisor;
maxSum += n;
}
return maxSum;
}
int main(){
int N = 12;
cout<<"The maximum sum after repeatedly dividing "<<N<<" by divisor is "<<calculateMaxSum(N);
return 0;
}
출력 결과
The maximum sum after repeatedly dividing 12 by divisor is 22
코드 설명
smallestDivisor 함수 − 2부터 √n까지의 수 중에서 n을 나누어 떨어지게 하는 가장 작은 수를 찾아 반환합니다. 만약 그런 수가 없다면 n은 소수이므로 n 자신을 반환합니다.
calculateMaxSum 함수 − 초기 합을 n으로 설정한 뒤, n이 1보다 클 동안 반복하면서 매번 최소 약수로 n을 나누고 그 몫을 합에 누적합니다. 루프가 끝나면 최종 합을 반환합니다.
이 알고리즘의 시간 복잡도는 각 나눗셈 단계에서 약수 탐색에 O(√n)이 걸리고, 총 나눗셈 횟수는 최대 log₂n이므로 전체적으로 O(√n · log n) 수준으로 효율적입니다.