문제
n의 각 자리 숫자를 모두 더하세요. 결과가 두 자리 이상이면, 그 숫자의 각 자리도 다시 더하세요. 한 자리 수가 남을 때까지 이 과정을 반복합니다.
digital_root(n)을 구현하세요.
입력
n: 양의 정수
출력
최종적으로 남은 한 자리 수를 반환하세요.
제약 조건
1 ≤ n ≤ 10¹⁸
예시
예시 1
입력:
n = 999
예상 출력:
expected = 9입력:
long long n = 999;
예상 출력:
long long expected = 9;입력:
long n = 999;
예상 출력:
long expected = 9;설명
9 + 9 + 9 = 27, 그 다음 2 + 7 = 9.
예시 2
입력:
n = 38
예상 출력:
expected = 2입력:
long long n = 38;
예상 출력:
long long expected = 2;입력:
long n = 38;
예상 출력:
long expected = 2;설명
3 + 8 = 11, 그 다음 1 + 1 = 2.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
자릿수를 계속 더하면 결국 한 자리 수로 줄어듭니다.
힌트 2
값이 10보다 작아질 때까지 반복해서 합을 구하면 됩니다.
힌트 3
입력이 아주 클 수 있으니 주의하세요. 과정은 단순하지만, 자릿수를 여러 번 훑는 것이 핵심입니다.
예상 복잡도
시간 O(d log n), 추가 공간 O(1)