[백준 온라인 저지] 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))), ...과 같은 무한 수열을 만들 수 있다.

n을 d(n)의 생성자라고 한다. 위의 예시에서 75는 87의 생성자이다. 생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

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

 

1. 입력

- 입력은 없다.

 

2. 출력

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

 

3. 예제

 

4. 코드

import java.io.*;
class Main {
    public static void main(String[] args) throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        // n[i] = true: 생성자가 있음
        boolean[] n = new boolean[10001];
        for(int i=0 ; i<=10000 ; i++){
            int j = next(i);
            while(j<=10000){
                if(n[j]) break;
                n[j] = true;
                j = next(j);
            }                
        }
        // next[i] == 0: i는 셀프 넘버
        for(int i=1 ; i<=10000 ; i++)
            if(!n[i]) bw.write(i+"\n");
        bw.flush(); bw.close();
    }
    
    static int next(int a){
        int num = a, tmp = a;
        while(tmp>0){
            num += tmp%10;
            tmp /= 10;
        }
        return num;
    }
}

- 14608KB, 152ms