(C++) 백준 4673 - 셀프 넘버

https://www.acmicpc.net/problem/4673

문제

> 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 
  예를 들어, d(75) = 75+7+5 = 87이다.
> 이를 이용해 무한 수열을 만들 수 있다.
  n, d(n), d(d(n)), d(d(d(n))), ...
> 33으로 시작한다면 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력해라.

접근

어떤 수가 들어오면 그 수를 매개로 수열이 많들어지기 때문에 재귀를 사용한다.
selfnumber함수를 만들어 셀프넘버를 판별해준다.
10000까지 순회하며 셀프넘버인 수를 출력한다.

문제해결

> 셀프넘버가 아닌 수를 판별하기 위해 bool로 벡터를 선언해준다. 함수 selfnumber를 정의해 생성자로 i를 받아 무한 수열을(10000이하까지) 만든다.
> 초기 i와, 각 자리를 더해 다음 수를 나타내는 num을 선언하고, 자릿수를 뽑아내기 위해 i를 변형시켜야 하므로 tmp를 선언해 자릿수 계산에 사용한다.
> 함수에서 재귀를 이용해 1부터 10000까지 해당 i로 들어온 수를 만들고 각 만들어진 수를 인덱스로 해 bool 값을 true로 주며 마킹한다.
> selfnumber함수에 1을 넣어 함수를 호출해준다. 그러면 알아서 i+1재귀로인해 정리된다.
> 1부터 10000까지 돌며 bool값이 false인 값, 즉, 함수를 통해 만들어진 적 없는수인 셀프넘버를 출력한다.

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int MAX = 10000;
vector<bool> selfnum(MAX +1, false);
void selfnumber(int i)
{
	if (i > MAX) return;

	int num = i;
	int tmp = i;
	while (tmp > 0)
	{
		num += tmp % 10;
		tmp /= 10;
	}
	if (num <= MAX)
		selfnum[num] = true;
	selfnumber(i + 1);
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	selfnumber(1);

	for (int i = 1; i <= MAX; i++)
	{
		if (!selfnum[i])
			cout << i << '\n';
	}
}

후기

문제가 혼동의 여지가 있어 잘못 이해해서 틀렸다.
n에 대해 d(n), d(d(n)), d(d(d(n)))...을 구한다길래 1만 넣어 1로 생성된 무한수열만 따지는 줄 알았다. 하지만 모든 수로 만들어진 수열을 다 따져야헀다.