[백준] 4673번 - Java(자바)

백준 4673번 자바

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

4673번: 셀프 넘버

 

 

문제내용은 아래 더보기를 누르면 나온다.

 

 

알고리즘

n은 양의 정수이다.

d(n)은 n과 n의 각 자리수를 더하는 함수이다.

e.g. d(75) = 75 + 7 + 5 = 87

이렇게 n을 d(n)의 생성자라고 하는데, 생성자가 없는 숫자를 셀프 넘버라고 한다.

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하시오.

 

 

1. d(n) 함수를 만든다.

2. 10000길이의 boolean 배열인 check[]를 만든다.

3. 10000번 반복한다. (for i = 1; i < 10001; i++)

    3-1. check[i] 가 false이면 d(i) 실행

4. 10000번 반복한다.

    4-1. check[i]가 false이면 출력

 

 

 

 

풀이1

public class Main {
    public static void main(String[] args) {
        boolean[] check = new boolean[10000];
        for (int i = 1; i <= 10000; i++) {
            int n = d(i);
            if (n <= 10000) check[n - 1] = true;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 10000; i++) {
            if(!check[i]) sb.append(i+1).append("\n");
        }
        System.out.println(sb);
    }

    static int d(int n) {
        int sum = n;
        while (n != 0) {
            sum += n % 10;
            n /= 10;
        }
        return sum;
    }
}

이 문제는 예전에 한 번 풀어서 기억이 났다.

https://st-lab.tistory.com/53 여기 블로그를 참고하여 풀었다.

그러다가 재귀함수처럼 풀어보면 어떨까싶어서 다시 풀이2로 작성해보았다.

 

 

 

풀이2

public class Main {
    static boolean[] check = new boolean[10001];

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < 10001; i++) {
            if (!check[i]) d(i);
        }

        
        for (int i = 1; i < 10001; i++) {
            if (!check[i]) sb.append(i).append('\n');
        }
        System.out.println(sb);
    }

    // 재귀함수
    static int d(int n) {
        int sum = n;
        while (n != 0) {
            sum += n % 10;
            n /= 10;
        }
        if (sum < 10001) {
            check[sum] = true;
            d(sum);
        }
        return sum;
    }
}

풀이1번에서 변형했다고보면 된다.

코드를 실행하면 처음 check[1]이 false일 경우 d(1)을 실행한다.

d(1) 메서드는 풀이1번처럼 진행을 한다.

sum에 1 + 1 = 2의 값을 넣는다.

sum이 10001보다 작으면 check[sum]을 true로 해주고 다시 d(sum)으로 메서드를 돌린다.

그렇게 진행하면 다음과 같이 된다.

2, 4, 8, 16, 23 .... 의 값들이 check[]의 인덱스로 들어가서 true로 바뀐다.

여기서 생각나는게 에라토스테네스의 체이다.

체로 치듯이 수를 걸러낸다고해서 이렇게 불리는데 지금 하는 방식과 매우 유사하다.

그렇게 d(n) 메서드가 끝나면 다시 main메서드로와서 check[2]를 보는데 이것은 아까전의 재귀함수로 true가 되어있으므로 넘어가게되고 check[3]을 보게된다.

 

글로 설명하니 이해하기 어려우니 다음 그림을 보자

먼저 check[1] = false이면 좌측 그림처럼 d(1) -> d(2) -> d(4) -> ..... 이렇게 진행된다.

진행하면서 우측 그림에 빨간색으로 저 칸들이 true가 되는 것이다. 

전부 빨간색으로 그어지면 다시 check[2]를 살펴본다.

check[2] = true이므로 넘어간다.

check[3] = false이므로 방금처럼 진행한다. d(3) -> d(6) -> d(12) -> d(15) -> ....

이 과정에서 다시 초록색으로 그어지고 반복된다.

 

이제 어떤 느낌인지 감이 올 것이라 믿는다.

뭔가 아리쏭하다면 에라토스테네스의 체를 검색하면 되겠다.