백준 4673 셀프넘버

Eunkyung·2021년 9월 29일
0

Algorithm

목록 보기
1/30

이해하는데 오래 걸렸던 셀프넘버
https://www.acmicpc.net/problem/4673

  1. 10000보다 작거나 같은 셀프 넘버 출력하기 위해 10000+1 배열 생성
boolean[] check = new boolean[10001];
  1. d(n)으로부터 n을 구하는 것보다 n으로부터 d(n)을 구하는 것이 쉬움
    ex) n = 1234일 경우
    d(n) = 1234+1+2+3+4=1244
  • 반복문을 이용하여 d(n) 구하는 방법
 public static int d(int number) {
        int sum = number; // sum = 1

        while (number != 0) {
            sum = sum + (number % 10); // 첫 째 자리수 sum = 2
            number = number / 10;    // 10을 나누어 첫 째 자리를 없앤다 number = 0
        }

        return sum; // 2
    }
  • 첫 번째 반복
    number % 10 = 4 -> sum = 1234 + 4 = 1238
    number / 10 =123 -> number = 123

  • 두 번째 반복
    number % 10 = 3 -> sum = 1238 + 3 = 1241
    number / 10 = 12 -> number = 12

  • 세 번째 반복
    number % 10 = 2 -> sum = 1241 + 2 = 1243
    number / 10 = 1 -> number = 1

  • 네 번째 반복
    number % 10 = 1 -> sum = 1243 + 1 = 1244
    number / 10 = 0 -> number = 0 반복 종료

  • 자기 자신 + 첫째 자리 수 + 둘째 자리 수 + 셋째 자리 수 + 넷째 자리 수 = 생성자

  1. 생성자인 경우 true값 반환하여 false인 값이 셀프넘버

전체 코드

public class b4673 {
    public static void main(String[] args) {
        /**
         * 생성자
         * 두 자리 수일 경우, 자기 자신 + 십의 자리 수 + 일의 자리 수
         * 셀프 넘버 : 생성자가 존재하지 않는 수
         */
        boolean[] check = new boolean[10001];    // 1부터 10000이므로

        for (int i = 1; i < 10001; i++) { // i = 1
            int n = d(i); // n = 2

            if (n < 10001) {    // 10000 이 넘는 수는 필요가 없음
                check[n] = true; // check[2] = true 셀프 넘버가 아닐 경우 false
            }
        }

        StringBuilder sb = new StringBuilder();

        for (int i = 1; i < 10001; i++) {
            if (!check[i]) {    // false 인 인덱스만 출력
                sb.append(i).append('\n');
            }
        }
        System.out.println(sb);
    }


    public static int d(int number) {
        int sum = number; // sum = 1

        while (number != 0) {
            sum = sum + (number % 10); // 첫 째 자리수 sum = 2
            number = number / 10;    // 10을 나누어 첫 째 자리를 없앤다 number = 0
        }

        return sum; // 2
    }
}

    
    
profile
꾸준히 하자

0개의 댓글