[JAVA] 백준 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. 코드

public class Main{
    public static void main(String[] args){
        boolean[] check = new boolean[10001];
        for(int i=1;i<10001;i++){
            int n = d(i);
            if(n<10001)	check[n]=true;
        }
        
        for(int i=1;i<10001;i++){
            if (check[i]==false)    System.out.println(i);
        }
        
    }

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

 

3. 풀이

d 함수는 n과 각 자리수를 더하는 함수이다.

d함수에 대한 설명은 아래 주석으로 달아놓았다.

public static int d(int n){
    int cnt=n;	//cnt는 n과 각 자릿수를 더한 값을 저장하기 위한 변수
    //cnt의 초기값을 n으로 한다.
    
    while(n!=0){
        cnt = cnt + (n%10);
        //기존의 cnt값에 n의 일의 자리수를 더해 저장한다. 
        //cnt의 초기값을 n으로 설정한 이유이다.
        
        n = n/10;
        //일의자리를 없애준다. 
    }
    	return cnt;	
	}
}

n/10을 함으로써 일의 자리를 없앤다는 것은 계산을 해보면 알겠지만,

1234 -> 123 -> 12 -> 1 -> 0 이렇게 된다. 

 

main함수로 돌아가면..

public class Main{
    public static void main(String[] args){
        boolean[] check = new boolean[10001];
        // true false값을 저장하는 bool타입 배열을 선언한다.
        
        for(int i=1;i<10001;i++){
            int n = d(i);	//i와 각 자릿수를 더한 값을 계산한 값을 n에 저장한다.
            
            if(n<10001)	check[n]=true;
            //결과값들 중에서 10001보다 작은 값들만 true로 설정한다. 
            
        }
        
        for(int i=1;i<10001;i++){
        	//false인 값들만 출력한다. -> false인 값들은 당연히 d함수를 통해 반환되지 않는 값들이다.
            if (check[i]==false)    System.out.println(i);
        }
        
    }

※ boolean 배열의 크기가 10001인 이유

이후 반복문에서 1에서 10000까지의 인덱스 숫자를 쓸 것이므로, check[10000]의 값을 저장하기 위해서는 배열의 크기를 [10001]로 설정해 주어야 한다.

 

※  if(n<10001) check[n]=true; 인 이유

만약 n 20000이라는 숫자가 나왔을때, if문이 없어 그대로 check[n]=true;라 실행했다면 , "java.lang.ArrayIndexOutOfBoundsException" 에러가 발생할 것이다. 즉, 배열의 인덱스 값이 범위를 넘어설 것이다. check 배열의 크기는 10001으로 설정되어있기때문에 n의 값이 10001보다 작은 경우에만 해당 실행문이 실행되도록 하면 된다. 

백준에서 실행시키게 되면 "런타임 에러"가 발생할 것이다. 

 

 

 

 

4. 링크

www.acmicpc.net/problem/4673

4673번: 셀프 넘버