[백준 BOJ 4673번] 셀프 넘버

출처 : https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

 

1. 문제

셀프 넘버는 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

---

2. 입력

입력 없음.

입력 없음.

---

3. 출력

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

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

---

4. 풀이

수학적인 규칙을 찾아보았다.

일일이 설명하기엔 복잡하지만 대략적으로 2, 11, 15 씩 주기를 갖고서 오름차순으로 셀프 넘버가 출력되는 것을 확인할 수 있었다. 하지만 이를 수학적인 접근으로 가는 것보다는 더 빠르고 쉽게 해결하는 것이 낫다는 생각을 하였다,

또한, 문제에서 언급된 d(n), d(d(n)),... 처럼 합성함수로 이어나가는 것보다는 차라리 10000이하의 자연수들을 대입하는게 문제 해결에 있어서 쉽게 접근하고 겹치는 경우가 더 적다고 판단되었다.

 

결론 : 미리 10,000까지의 index들이 모두 true 값을 갖는 Boolean형 배열을 생성한다. 이후 1~10,000 까지의 자연수들을 d(n)에 넣어서 d 함수의 return 값과 같은 index의 Boolean 배열 요소들에 false 값을 넣어준다. 모든 과정이 끝나면 true값을 갖는 배열 요소들의 index값들을 출력한다.

---

5. 소스코드

import java.io.*;

class Main{
    public static void main(String [] args) throws IOException {
        Boolean [] tf = new Boolean [10001];
        for(int i=1; i<10001; i++){
            tf[i] = true;
        }
        for(int i=1; i<10001; i++){
            if (d(i) > 10000) continue;
            tf[d(i)] = false;
        } 

        for(int i=1; i<10001; i++){
            if(tf[i] == true){
                System.out.println(i);
            }
        }
    }

    public static int d(int a){
        String str_a = Integer.toString(a);

        int sum = 0;
        sum += a;
        for(int i=0; i<str_a.length(); i++){
            sum += Character.getNumericValue(str_a.charAt(i));
        }
        return sum;
    }
}

---

6. 배운 것

정수의 각 자리수들을 나누는 방식을 '10으로 나눈 나머지와 몫' 방식을 이용하지 않고 String형 변수를 charAt()함수를 사용하여 각 자리수를 가져와서 int형으로 변형하여 더해주었다. 이때 char형에서 int형으로 바꾸는 방법은 Character.getNumericValue(char형 값)을 통해 형변환하는 방식으로 했다.

 

다른 char to int 형변환 방법으로는 주어진 char 값에서 '0'을 빼주는 ASCII code를 활용한 방식도 있다.

 

ex) char a = '9';

int b = a - '0';