재미주의 프로그래밍(funnism.com) :: 셀프넘버(self-number) 문제

Software/자료구조&알고리즘2009/10/14 14:23

셀프넘버(self-number) 문제

어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101
이때, n을 d(n)의 “제너레이터”(generator)라고 한다. 위의 예에서 91은 101의 제너레이터이다. 어떤 숫자들은 하나 이상의 제너레이터를 가지고 있는데, 101의 제너레이터는 91뿐만이 아니라 100도 있다. (1 + 0 + 0 + 100 = 101)
그런데 반대로, 제너레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 “셀프 넘버”(self – number)라 이름 붙였다.
예를 들어 1, 3, 5, 7, 9, 20, 31… 은 셀프 넘버들이다.

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

소스보기

#include
#include
using namespace std;

int d(int num)
{
	int arr[100] = {0, };

	int i=0;

	arr[i++] = num;
	while(num != 0){
		arr[i] = num % 10;
		num = num / 10;
		i++;
	}
	
	int sum = 0;
	for(int j=0; j < i; j++){
		sum += arr[j];
	}

	return sum;
}

int main()
{
	int input = 0;
	cout << "셀프넘버의 합을 구하려는 숫자 : ";
	cin >> input;
	vector vecNum;
	vecNum.reserve(input);
	vecNum.assign(input, 0);

	for(int i=0; i < input; ++i){
		vecNum[i] = i+1;
	}

	int offset = 0;
	offset = d(1)-1;
	for(int i=2; offset < input; i++){
		vecNum[offset] = -1;
		offset = d(i)-1;
	}

	int sum = 0;
	for(int j=0; j < input; j++){
		if(vecNum[j] != -1){
			sum += vecNum[j];
			cout << vecNum[j] << " ";
		}
	}
	cout << endl;
	cout << "셀프넘버의 합 : " << sum << endl;

	return 0;
}