[백준] 4673 셀프 넘버

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

셀프 넘버란?

1949년 인도 수학자 D.R.Kaprekar 가 만든 것이다. 양의 정수 x에 대해 d(x) 를 x와 x의 각 자리수를 더하는 함수라고 정의 한다. 예를 들어 44는 44+4+4=52 이고, 52는 52+5+2=59 이다. 이런 식으로 계속 진행할 경우, x를 d(x) 의 생성자라고 정한다. 52는 59의 생성자이고, 44는 52의 생성자이다.

이같은 함수를 정의할 경우, 생성자가 없는 숫자를 셀프 넘버라고 정의한다.

이 문제의 알고리즘 분류를 볼 때, 에라토스테네스의 체를 이용하라고 나온다. 즉, 이 알고리즘을 사용해야지 메모리 제한이나 시간 제한에 걸리지 않는다는 것이다.

(에라토스테네스의 체 : 소수를 판별할 때 자주 쓰는 알고리즘이다. 2를 제외한 2의 배수 삭제, 3을 제외한 3의 배수 삭제, 4는 2의 배수에서 삭제 되었으니 통과, 5를 제외한 5의 배수 삭제....이 과정을 반복하게 되면 소수만 남게 되는 알고리즘이다.)

나는 어떠한 배열의 위치를 셀프 넘버를 판별하는 수로 생각하고, 배열 안의 내용을 0과 1로 나누어서 셀프 넘버인지 아닌지 판별하는 알고리즘을 생각해 보았다. d(x) 를 생성하는 함수를 모듈화 시킨 다음, 10000이 되기 전까지 실행시킨다. 이 과정을 1~10000까지 반복하면, 셀프 넘버만 남게 된다는 생각이다. 이러한 원리로 프로그램을 짜 보았다.

#include <stdio.h>
 
int arr[10001];
 
int self(int num) //d(x) 만드는 함수
{
    int a,b,c,d;
    a=num/1000;
    b=(num-1000*a)/100;
    c=(num%100)/10;
    d=num%10;
    return num+a+b+c+d;
}
 
int main()
{
    int temp;
    for(int i=1;i<=10000;i++)  //1부터 10000까지 셀프 넘버 기록 
    {
        temp=i;
        while(temp<10000)
        {
            if(arr[i]==0)
            {
                arr[self(temp)]=1;  //해당 수(셀프 넘버)를 제외한 나머지 거르기
            }
            temp=self(temp);
        }
    }
    
    for(int i=1;i<=10000;i++)  //셀프 넘버 출력 
    {
        if(arr[i]==0)
        {
            printf("%d\n",i);
        }
    }
 }