BOJ 2145 - 숫자 놀이

문제

BOJ 2145 - 숫자 놀이

자연수가 주어지면 각 자릿수를 더하는 과정을 한 자리 수가 될 때까지 반복하라. 0이 입력되면 종료한다.

입력

여러 줄에 자연수가 주어지며, 0이면 종료한다.

출력

각 수에 대해 최종 한 자리 수를 출력한다.

예제

풀이

각 자릿수의 합을 구하는 과정을 한 자리가 될 때까지 반복한다 (디지털 루트).

1. 수가 9보다 크면 각 자릿수를 분리하여 합산한다
2. 합이 다시 10 이상이면 반복한다
3. 한 자리 수가 되면 출력한다

핵심 아이디어: 각 자릿수 합을 반복하면 매번 자릿수가 크게 줄어들어 빠르게 수렴한다.

코드

while(True):
    n = int(input())
    if n == 0:
        break
    while(n>9):
        n = sum(map(int,list(str(n))))
    print(n)

복잡도

• 시간: O(log N) — 자릿수 합 반복 횟수
• 공간: O(log N) — 자릿수 분리 시 문자열 변환