백준 - 4673 셀프 넘버

본 문제의 요구사항은 다음과 같다

 

임의의 숫자 n 에서 n 을 구성하는 각자리숫자의 합을 d(n) 이라고 한다.

예를 들면 d(15) = 15 + 1 + 5 = 21 이다.

n 은 d(n) 의 생성자라고 한다. 즉 15는 21의 생성자이다.

임의의 숫자 m 이 생성자가 없다면 이러한 숫자를 셀프넘버라고 한다. 

10000 보다 작거나 같은 모든 셀프넘버를 한줄에 하나씩 출력해야 한다.

 

본문제의 풀이과정은 다음과 같다. 10001 개의 배열을 잡고 0으로 초기화 한다.

n 은 d(n) 보다는 무조건 작기때문에 1부터 10000 까지만 d(n) 을 구한다. 배열의 d(n) 에 해당되는 index 의 값을 1로 세팅한다.

모든 d(n) 계산 완료후 배열에서 0 인 값의 index 의 집합이 셀프넘버의 집합이 된다.

 

각자리수의 합을 구하기 위해서는 나머지 연산과 나눗셈 연산의 조합으로 구할수 있다.

 

예를 들면 1234 의 각 자릿수의 합을 생각해 보면 아래와 같다.

 

1234 % 10 = 4       --> 1의 자리수 획득

1234 / 10 = 123

123 % 10 = 3        --> 10의 자리수 획득

123 / 10 = 12

12 % 10 = 2         --> 100의 자리수 획득

12 / 10 = 1

1 % 10 = 1          --> 1000의 자리수 획득

1 / 10  = 0          --> 종료

 

값이 0 이 될때까지 10으로 나머지 연산과 나누기 연산을 반복하여 도출된 각자리수의 합을 더하면 된다.

아래 코드의 digiSum 함수처럼 구현할 수 있다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

void process();

int digitSum(int n);

int main()
{
	int data[10001] = { 0, };

	for (int i = 1; i < 10000; i++)
	{
		int cNum = digitSum(i) + i;
		if (cNum <= 10000) data[cNum] = 1;
	}

	for (int i = 1; i <= 10000; i++)
	{
		if (data[i] == 0) cout << i << endl;
	}
}

int digitSum(int n)
{
	int result = 0;
	while (n)
	{
		result += n % 10;
		n /= 10;
	}
	return result;
}