1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하기

문제 출처 : 넥슨입사문제

 

 

※ 문제 

어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자.

 

예를 들어

 

d(91) = 9 + 1 + 91 = 101

 

이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다.

 

어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.

 

1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

 

※ 풀이

위의 문제를 풀기 위해서는 제너레이터를 구하는 규칙을 찾아

1~5000까지 제너레이터 숫자를 제외한 숫자를 더하면 셀프 넘버들의 합이 된다.

 

먼저 제네레이터가 존재하는 숫자를 구하는 규칙을 살펴보자

 

자연수 n	d(n)	자릿수 숫자	자기 자신 n	합계 (제네레이터가 존재)
1	d(1)	1	1	2
2	d(2)	2	2	4
3	d(3)	3	3	6
21	d(21)	2+1	21	24
91	d(91)	9+1	91	101
...	...	...	...	...
5000	d(5000)	5+0+0+0	5000	5005

 

n에 들어가는 숫자에 자릿수를 더하고 자기자신을 더했을 때 합계금액이 제네레이터가 존재하는 숫자이다.

 

셀프넘버는 제네레이터가 존재하지 않는 숫자이므로 

합계 금액이 1부터 시작한다고 할 때 위의 합계 금액에 없는 자연수가 셀프 넘버들이 된다.

 

위의 규칙을 토대로 제네레이터가 존재하는 자연수를 찾고 1~5000까지 제네레이터를 가지고 있는

숫자를 포함하지 않는 자연수를 찾아 더하면 1~5000까지의 셀프 넘버들의 합이 된다.

 

 

※ 소스코드

public class AlgoTest { 	
	public static void main(String[] args){ 		
		ArrayList<Integer> arr = new ArrayList<Integer>();  		
		//제네레이터가 존재하는 자연수 찾기 		
		for(int i=0; i<= 5000;i++){ 			
			String findGenVal = String.valueOf(i); 			
			int nLength = findGenVal.length(); 			
			int cipherSum = 0; 			 
			
			//자릿수를 더한 값 구하기 			
			for(int n=0; n< nLength;n++){ 				
				cipherSum += Integer.parseInt(findGenVal.substring(n, n+1); 		
			}  			
			//자릿수를 더한 값에 자기 자신 더하기 			
			//(제네레이터가 존재하는 숫자) 			
			arr.add(cipherSum + i); 			 		
		}  		
		int sum = 0; 		
		for(int i=0; i<=5000;i++){ 			
			//1~5000까지 제네레이터가 존재하는 숫자를 포함하지 않는 자연수 더하기 			
			if(arr.contains(i) == false){ 				
				sum += i; 			
			} 		
		}  		
		
		System.out.println("### 셀프 넘버들의 합 : " + sum);  	
	} 
}