이 튜토리얼에서는 주어진 숫자가 한 자릿수로 줄어들 때까지 자릿수의 합과 곱을 반복해서 계산하고, 그 결과 중 최대값을 구하는 프로그램을 C++로 작성하는 방법을 다룹니다.
문제의 조건은 다음과 같습니다. 임의의 정수 하나가 주어지면, 그 숫자의 각 자릿수를 더한 값과 곱한 값을 각각 구합니다. 만약 그 결과가 여전히 두 자릿수 이상이라면, 같은 과정을 한 자릿수가 될 때까지 반복합니다. 최종적으로 얻어진 두 개의 한 자릿수 값 중에서 더 큰 값을 출력하면 됩니다.
핵심 아이디어
자릿수의 반복 합(repeated sum)은 소위 '디지털 루트(digital root)'라고 불리는 개념으로, 수학적으로 잘 알려진 성질 덕분에 반복문 없이 O(1)에 계산할 수 있습니다. 어떤 수를 9로 나눈 나머지를 활용하면 되는데, 나머지가 0인 경우에는 결과가 9가 된다는 점만 주의하면 됩니다.
반면 자릿수의 반복 곱(repeated product)은 간단한 공식이 없으므로, 실제로 자릿수를 하나씩 곱해 가며 한 자릿수가 될 때까지 반복 처리해야 합니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
// 자릿수를 반복해서 더하여 한 자릿수로 변환
double repeatedSum(long n) {
if (n == 0)
return 0;
// 디지털 루트 공식: 9로 나눈 나머지 활용
return (n % 9 == 0) ? 9 : (n % 9);
}
// 자릿수를 반복해서 곱하여 한 자릿수로 변환
long repeatedProduct(long n) {
long prod = 1;
while (n > 0 || prod > 9) {
// n이 0이 되었는데 prod가 아직 두 자릿수라면
// prod를 새로운 n으로 삼아 다시 곱셈 진행
if (n == 0) {
n = prod;
prod = 1;
}
prod *= n % 10;
n /= 10;
}
return prod;
}
// 합과 곱의 결과 중 최대값 반환
long maxSumProduct(long N) {
// 이미 한 자릿수라면 그대로 반환
if (N < 10)
return N;
return max(repeatedSum(N), repeatedProduct(N));
}
int main() {
long n = 631;
cout << maxSumProduct(n) << endl;
return 0;
}실행 결과
8
동작 원리 살펴보기
입력값이 631일 때 프로그램이 어떻게 동작하는지 단계별로 확인해 보겠습니다.
반복 합의 경우: 6 + 3 + 1 = 10이 되고, 10은 아직 두 자릿수이므로 다시 1 + 0 = 1로 줄어듭니다. 최종 결과는 1입니다.
반복 곱의 경우: 6 × 3 × 1 = 18이 되고, 18 역시 두 자릿수이므로 다시 1 × 8 = 8로 계산됩니다. 최종 결과는 8입니다.
두 결과를 비교하면 max(1, 8) = 8이므로, 프로그램은 8을 출력하게 됩니다.
마무리
이 예제는 반복 합에서 수학적 성질(9의 나머지 법칙)을 활용하면 연산 횟수를 크게 줄일 수 있다는 점, 그리고 반복 곱은 조건문과 while 루프를 적절히 조합해 해결할 수 있다는 점을 보여주는 좋은 사례입니다. 자릿수 연산과 관련된 다양한 응용 문제에도 같은 접근 방식을 활용할 수 있으니, 코드를 직접 변형해 보면서 개념을 익혀 보시기 바랍니다.