슈퍼 자릿수(Super Digit)란?
하나의 숫자 n이 주어졌을 때, 이 수의 슈퍼 자릿수(super digit)를 구해야 합니다. 슈퍼 자릿수는 다음과 같이 정의됩니다.
- 한 자리 숫자의 슈퍼 자릿수는 그 숫자 자신입니다.
- 여러 자리 숫자의 경우, 각 자릿수의 합을 구하고, 그 합이 한 자리 숫자가 될 때까지 이 과정을 반복한 최종 결과가 슈퍼 자릿수입니다.
예를 들어 입력이 n = 513682라면 결과는 7이 됩니다.
(5+1+3+6+8+2) = 25 → (2+5) = 7
해결 접근 방법
이 문제는 다음 단계에 따라 해결할 수 있습니다.
- s := 0 으로 초기화합니다.
- n > 0 또는 s > 9인 동안 아래를 반복합니다.
- n이 0이라면, n := s 로 바꾸고 s := 0 으로 초기화합니다. (자릿수 합을 새로운 대상으로 사용)
- s := s + (n mod 10) — 마지막 자릿수를 더합니다.
- n := n / 10의 몫(내림) — 마지막 자릿수를 제거합니다.
- 반복이 끝나면 s를 반환합니다.
파이썬 구현 예제
def solve(n):
s = 0
while(n > 0 or s > 9):
if n == 0:
n = s
s = 0
s += n % 10
n //= 10
return s
n = 513682
print(solve(n))입력
513682
출력
7
동작 원리 살펴보기
위 코드에서 while 루프의 조건이 중요합니다. n > 0만 확인하면 자릿수 합(s)이 아직 두 자리 이상일 때 반복이 멈출 수 있습니다. 따라서 s > 9 조건을 함께 검사하여, 합계가 한 자리 숫자가 될 때까지 연산을 이어갑니다.
또한 n이 0이 되었을 때 누적된 s를 새로운 n으로 대체하는 방식 덕분에, 재귀 호출 없이 하나의 루프만으로 전체 과정을 처리할 수 있어 효율적입니다.
참고: 디지털 루트(Digital Root)
슈퍼 자릿수는 수학에서 말하는 '디지털 루트'와 같은 개념입니다. 흥미롭게도 디지털 루트는 나머지 연산을 이용해 O(1) 시간에 구할 수도 있습니다.
def digital_root(n):
return 0 if n == 0 else 1 + (n - 1) % 9
print(digital_root(513682)) # 7n이 양수일 때 결과는 1 + ((n - 1) mod 9)와 항상 같습니다. 이 성질을 활용하면 매우 큰 숫자도 즉시 슈퍼 자릿수를 계산할 수 있습니다.