[백준] 4673 셀프 넘버

self_num = [False]+[True]*10000
for number in range(1,10001):
    tmp = number + (number//10000) + (number//1000)%10 + (number//100)%10 + (number//10)%10 + (number) % 10
    if tmp<=10000:  # 생성자가 하나라도 있으면 False
        self_num[tmp] = False

for number, isselfnum in enumerate(self_num):
  if isselfnum:
      print(number)

수열 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의했다. 

우리가 풀어야할 문제는 생성자가 없는 셀프넘버를 찾는 것이다. (n은 d(n)의 생성자)

문제를 봤을 때 에라토스테네스의 체가 생각났다. 낮은수부터 올라가며 소수는 남기고 소수의 배수들은 제거하는 알고리즘이다.

이 방법을 사용하면 1부터 N까지의 생성자를 가지는 수열 d(N)을 확인할수 있을 것이다.

각 인덱스 별로 True를 원소로 가지는 1차원 배열을 만들고 생성자가 있는 인덱스를 False로 체크해서 셀프넘버를 찾았다.