Jun 20 2008

‘셀프 넘버’ 문제

분류: Dev.Programming 태그: ,, — Heart @ 4:44 오후

Trackback : http://dev.heartsavior.net/archives/149/trackback/

넥슨 입사시험 문제로 더 유명한 ‘셀프 넘버’ 문제

어떤 자연수 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 보다 작은 모든 셀프 넘버들의 합을 구하라

이게 문제인데…

규칙이 있을꺼라 생각하고 규칙을 찾아보려고 머리를 굴려 봐도, self number를 뽑아서 봐도…
아무리 생각해도 규칙을 못찾겠다 OTL

단지, self number 간의 차가 2가 몇 번 나오다가 11 여러 번, 12 한 번, 다시 11 여러 번 나온다는 정도?

그래서, 그냥 1 ~ 5000 까지의 수로 d(n)을 전부 만들어보는 방법을 사용했다.
자기 자신을 한 번 더하기 때문에 5000 이상은 계산할 필요가 없다.

?View Code CPP
#include <iostream>
using namespace std;
 
#define MAX_NUMBER		5000
 
bool g_selfNumber[MAX_NUMBER + 1];
 
void initSelfNumberArr();
int funcGenerator(int number);
 
int main(void)
{
	int sum = 0;
 
	initSelfNumberArr();
 
	for( int i = 1 ; i < = MAX_NUMBER ; i++ )
	{
		int generator = funcGenerator(i);
 
		if( generator <= MAX_NUMBER )
			g_selfNumber[generator] = false;
	}
 
	for( int i = 1 ; i <= MAX_NUMBER ; i++ )
	{
		if( g_selfNumber[i] == true )
		{
			//cout << "Self Number found : " << i << endl;
			sum += i;
		}
	}
 
	cout << "Sum of self number (1~" << MAX_NUMBER << ") is " << sum << endl;
 
	return 0;
}
 
void initSelfNumberArr()
{
	for( int i = 0 ; i <= MAX_NUMBER ; i++ )
		g_selfNumber[i] = true;
}
 
int funcGenerator(int number)
{
	int total = 0;
 
	int n = number, mod;
 
	do {
		mod = n % 10;
		n = n / 10;
 
		total += mod;
	} while( n > 0 );
 
	total += number;
 
	return total;
}
</iostream>