BOJ04673 셀프 넘버

https://www.acmicpc.net/problem/4673 (opens new window)

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자.

양의 정수 n이 주어질 때 이 수를 시작해서 n, d(n), d(d(n)) ... 과 같은 무한 수열을 만들 수 있다.

33 + 3 + 3 = 39
39 + 3 + 9 = 51
51 + 5 + 1 = 57
...

n은 d(n)의 생성자이다. 33은 39의 생성자이다. 51은 57의 생성자이다. 생성자는 한 개보다 많을 수 있다.

생성자가 없는 숫자를 셀프 넘버라고 한다. 10000보다 작거나 같은 셀프 넘버를 출력한다.

d 메소드

생성자를 구하기 위한 메소드이다.

private static int d(int n) {
    String[] digits = String.valueOf(n).split("");
    int sum = n;

    for (String digit : digits) {
        sum += Integer.parseInt(digit);
    }

    return sum;
}

위에서 작성한 d 메소드를 활용하여 생성자가 있는 인덱스를 true로 설정한다.

for (int i = 1; i <= 10_000; i++) {
    if (d(i) <= 10_000) {
        isConstructor[d(i)] = true;
    }
}

마지막으로 배열을 모두 탐색하며 생성자가 존재하지 않으면 해당 index를 출력한다.

for (int i = 1; i <= 10_000; i++) {
    if (!isConstructor[i]) {
        System.out.println(i);
    }
}

아래는 최종 제출 코드이다.

public class BOJ4673 {

    public static void main(String[] args) {

        boolean[] isConstructor = new boolean[10_001];

        for (int i = 1; i <= 10_000; i++) {
            if (d(i) <= 10_000) {
                isConstructor[d(i)] = true;
            }
        }

        for (int i = 1; i <= 10_000; i++) {
            if (!isConstructor[i]) {
                System.out.println(i);
            }
        }
    }

    private static int d(int n) {
        String[] digits = String.valueOf(n).split("");

        int sum = n;
        for (String digit : digits) {
            sum += Integer.parseInt(digit);
        }

        return sum;
    }
}

#algorithm #BOJ #수학 #구현