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 복사

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

 

 

---

흠... 일단 문제가 너무 이해가 안갔다... 그래서 끄적끄적 코드를 쳐보니 

natural = set(range(1, 10001)) 
generated = set() 

for n in range(1, 10001):
    for j in str(n):
        n += int(j) 
        
    generated.add(n) 
self_num = sorted(natural - generated) 
for i in self_num:
    print(i)

 

1. 자연수 1~ 10000을 natural set에 넣어준다. 이 친구는 생성자가 없는 숫자를 골라내기 위한 용도로 쓰인다.

2. generated set는 d(n)들을 넣어줄 set이다. 빈방 상태로 시작한다.

3. 첫 번째 for문을 돌린다. 1부터 10000까지 돌리는 이유는, 1부터 10000 사이에서 나올 수 있는 생성자를 빠짐없이 찾기 위해서다. 문제에 있는 것처럼 d(d(d(... n)))수열식으로 꼬리 물면서 찾으면, 시작점에 따라 수열이 달라지는 셀프 넘버의 특성상 코드가 복잡해진다.

 

어.. 그래... 1부터 10000까지 계산한다고 하자.... generated set에 들어가는 숫자가 중복될 수 있으면,,, 101 같은 경우는 생성자가 2갠데 어떡해? -> 이는 중복을 허용하지 않는 set으로 해결

 

4.  그럼 이제 두 번째 for문을 보자. n를 str(n)으로 바꿨다!! -> indexing 해서 자릿수 씹고 뜯고 맛보려고...!

그리고 indexing 되어 한 글자씩 뽑힌 j를 int(j)로 형 변환해준다. -> 사칙연산하려고..!... n += int(j) 하려고...!

이렇게 각 자릿수를 원래 자기 수 n에 더해주면서 d(n)이 생성!

5. 이 d(n)은 set에 인자를 넣어주는 add()를 사용해서 generated에 집어넣어 준다.

6. 그럼 이제 1부터 10000까지의 수가 들어있는 natural에서 생성자가 있는 d(n)들을 모조리 빼준다.

출력할 때 순서대로 나와야 하니까 sorted로 정렬도 해준다.

그럼.. 생성자 없는 self_num set이 완성....

for문으로 self_num 하나씩.. 하나씩 출력하면 끝