[Python] 4673번 셀프 넘버 - 백준

셀프 넘버

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

---

 

풀이

Python을 이용한 풀이

 

풀이 1

로그인

 

def f(x):
    q = x + 1
    while q:
        q, r = divmod(q, 10)
        x += r
    return x


l = 10000
a = [True] * l
for i in range(l):
    try:
        a[f(i)] = False
    except:
        continue
for i, _ in enumerate(a, 1):
    if _:
        print(i)

 

문제의 요구사항은 10,000 이하의 '셀프 넘버'를 순서대로 출력하는 것이기에 생성자를 가지는 수를 걸러주는 작업을 거친다. 너비우선탐색과 에라토스테네스의 체를 참고하는 풀이다.

 

10000 길이(index: 0 ~ 9999)의 list를 모두 '참'값을 가지도록 만들어준다. list의 index는 모든 수에서 1을 뺀 값과 같다. 인자에서 1을 더한 생성자의 1의 자리부터 제일 높은 자리 수까지의 합을 구한 뒤에 index로 쓰기 위한 1을 뺀 값을 반환한다. 반환받은 값의 자리를 '거짓'으로 바꿔준다. 이 과정을 거치면서 분명 index보다 큰 값을 반환받을 경우도 존재하기에 try, except를 사용해서 index오류가 생기면 다음 순서로 넘겨준다. 이유는 전보다 높은 값을 인수로 넣는다고 해서 더 높은 값을 반환 받지는 않기에 반복문을 모두 돌아야 한다. 물론 뒤로 갈수록 버리는 값이 많아질 것이다. '참' 값을 가지는 셀프 넘버를 모두 구했다면 이제 enumerate를 사용해서 '참'값을 가진 index에서 1을 더한 값을 모두 출력한다.