[C++] 셀프넘버 : 4673번

문제

 

양의 정수 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

---

풀이

#include <iostream>
using namespace std;

bool IsSelfNumber(int x); // 셀프 넘버인지 찾는 함수
int GetDn(int x); // D(n) 을 구하는 함수

int main()
{
	for (int i = 1; i < 10000; i++)
	{ // 1부터 9999까지 셀프넘버인지 확인하기
		if (IsSelfNumber(i)) // 셀프넘버가 맞다면?
		{
			cout << i << "\n"; // 해당 셀프넘버 출력
		}
	}
}

bool IsSelfNumber(int x)
{
	int count = 0; // count 가 1개라도 있으면 셀프넘버가 아니다
	for (int i = 1; i <= x; i++)
	{ // 1부터 넘겨받은 x까지 돈다
		if (x == GetDn(i)) // 어떤 수를 D(n) 한 값이 x가 되면
		{					// x 는 셀프넘버가 아니다.
			count += 1;		// 따라서 구별을 위해 count 증가
			break;			// 더 돌 필요가 없음.
		}
	}
	if (count == 0) return true; // 한개도 없다면 셀프넘버가 true
	else return false;
}

int GetDn(int x)
{
	int dn = x; // 처음 x를 일단 더하고

	while (x != 0) // x를 계속 10으로 나눌건데 더이상 0이 아닐때까지
	{
		dn += x % 10; // 1의자리를 추출해서 더하고
		x = x / 10; // x 에는 1의자리가 빠진 (오른쪽으로 밀린) 숫자가 대입
	}
	return dn; // 결과 반환
}

 

1. 셀프 넘버가 되기 위해서는 생성자가 존재하지 않아야 한다.

2. 생성자가 있는지 없는지 판별하기 위해서는

숫자 X 보다 작은 모든 수의 D(x) 를 구해보면서, 원래의 숫자 X와 일치하는 것이 한 개라도 존재하는지 알아본다.

 

즉, 어떤 수의 D(n)이 내가 판별하던 수 X 와 같으면, X는 생성자가 존재하기에 셀프넘버가 아니다.

 

3. 9999까지 반복문을 돌면서 그 수가 어떤 수의 D(n) 이 되는지 확인한다.

4. 만약 어떤 수도 D(n)이 되지 않는다면 그 수는 셀프 넘버가 되므로 결과를 출력한다.

 

 

+ 다시 보니, 10000 보다 작거나 같은이다. 반복문을 도는 조건이 <= 10000 이 되어야 하겠지만

10000은 셀프넘버가 아닌 것을 알기에 수정하진 않았다.