문제 개요
두 개의 정수 number와 repeat가 입력으로 주어집니다. 목표는 입력 숫자를 repeat번 반복해 이어 붙여 만든 수의 각 자릿수를 모두 더하고, 그 합이 한 자리 숫자가 될 때까지 같은 과정을 반복하는 것입니다.
예를 들어 입력 숫자가 123이고 repeat=2라면, 123123의 자릿수 합은 1+2+3+1+2+3=12가 됩니다. 12는 아직 한 자리 숫자가 아니므로 다시 12의 자릿수 합인 1+2=3을 계산합니다. 따라서 최종 출력값은 3입니다.
입력·출력 예시
예시 1
입력 — number=32, repeat=3
출력 — 반복 이어붙이기로 형성된 숫자의 재귀적 자릿수 합: 6
설명 — 323232의 자릿수 합은 3+2+3+2+3+2=15이고, 15의 자릿수 합은 1+5=6입니다. 6은 한 자리 숫자이므로 최종 출력은 6이 됩니다.
예시 2
입력 — number=81, repeat=4
출력 — 반복 이어붙이기로 형성된 숫자의 재귀적 자릿수 합: 9
설명 — 81818181의 자릿수 합은 1+8+1+8+1+8+1+8=36이고, 36의 자릿수 합은 3+6=9입니다. 9는 한 자리 숫자이므로 최종 출력은 9가 됩니다.
알고리즘 접근 방식
- 정수형 변수 number와 repeat를 선언하고, 두 값을 함수 Recursive_Sum(number, repeat)에 전달합니다.
- Recursive_Sum(int number, int repeat) 함수 내부에서:
- 정수형 변수 total을 선언하고 repeat * sum(number) 값으로 초기화합니다.
- sum(total)의 반환값을 그대로 반환합니다.
- sum(int number) 함수 내부에서:
- number가 0이면 0을 반환합니다.
- number % 9가 0이면 9를 반환합니다.
- 그 외의 경우에는 number % 9를 반환합니다.
- 최종 결과를 출력합니다.
핵심 원리: 디지털 루트(Digital Root)
이 풀이의 핵심은 디지털 루트(digital root) 성질입니다. 어떤 수를 반복해서 자릿수 합을 구해 한 자리 숫자로 만든 결과는 원래 수를 9로 나눈 나머지와 같습니다(단, 나머지가 0일 때는 9). 또한 여러 번 이어 붙인 수의 자릿수 합은 "원래 수의 자릿수 합 × 반복 횟수"와 같으므로, 실제로 거대한 문자열을 만들 필요 없이 곱셈만으로도 빠르게 답을 구할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int sum(int number){
if(number == 0){
return 0;
}
if(number % 9 == 0){
return 9;
}
else{
return number % 9;
}
}
int Recursive_Sum(int number, int repeat){
int total = repeat * sum(number);
return sum(total);
}
int main(){
int number = 12;
int repeat = 4;
cout<<"Recursive sum of digits of a number formed by repeated appends is: "<<Recursive_Sum(number, repeat);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Recursive sum of digits of a number formed by repeated appends is: 3
number=12, repeat=4인 경우, 12121212의 자릿수 합은 1+2+1+2+1+2+1+2=12이고, 다시 12의 자릿수 합은 1+2=3이므로 최종 결과는 3입니다.