백준 온라인 저널, 구현, 수학/4673번 : 셀프 넘버(파이썬)

문제 정의

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

 

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

 

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

 

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

 

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

 

입력

입력은 없다.

 

 

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

 

예제 출력 1

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

- 이전에 탐색했던 숫자가 나올 경우 이후 탐색하게될 숫자는 이전에 탐색한 숫자들과 동일하기에 탐색하지 않은 숫자들에 대해서만 탐색한다.

 

 

접근 방법

1. 10000까지의 숫자를 방문처리하며 주어진 숫자를 셀프 넘버 공식에 맞게 처리한다.

2. 이때 한번 탐색한 숫자는 더이상 탐색하지 않고 반복문을 멈추고 다음 숫자로 넘어간다.

 

 

코드

import sys
# 재귀함수로 풀 예정이기에 재귀 깊이 조정
sys.setrecursionlimit(10**6)

# 이전에 탐색했던 숫자가 나올 경우 이후 탐색하게될 숫자는 이전에 탐색한 숫자와 동일하기 때문에 탐색하지 않은 숫자들에 대해서만 탐색
# 이를 위해 방문 처리를 확인하기 위한 리스트 생성
visited = [False] * 10000

# 생성자 확인
def generator(n):
    # 주어진 n에 대해 d(n)을 계산
    result = n
    for i in range(len(str(n))):
        # 이때 n에 그대로 더할 경우 값이 변할 수 있으므로 다른 변수에 저장
        result += int(str(n)[i])

    # n이 10000 이상일 때 탐색 종료        
    if result > 10000:
        return
    
    # 아직 탐색하지 않은 숫자일 경우 탐색 
    elif visited[result-1] == False:      
        # 해당 숫자 방문 처리
        visited[result-1] = True
        generator(result)

# 1회부터 10000회까지 생성자 함수 실행
for i in range(1, 10000):
    generator(i)    

# 방문하지 않은 값 출력
for i in range(10000):
    if visited[i] == False:
        print(i+1)