[BOJ 2231] 분해합 , [BOJ 4673] 셀프 넘버

분해합 : https://www.acmicpc.net/problem/2231

분류 : 브루트 포스

 

셀프 넘버 : https://www.acmicpc.net/problem/4673

분류 : 에라토스테네스의 체

 

두 문제가 유사한 부분이 있어서 같이 설명하려고 한다.

 

분해합

입력된 수가 되게 하는 생성자를 찾는 문제이다. (생성자 : 원래 수와 각 자리 수의 합 => 분해합)

예를 들어 216의 생성자로 198과 207이 될 수 있다.

198 + 1 + 9 + 8 = 216

207 + 2 + 0 + 7 = 216

 

생성자를 찾기 위해서 1~n까지 모든 수의 분해합이 N이 되는지 확인하는 방법도 있겠지만, 좀 더 최적화 할 수 있는 방법이 있다.

각 자리숫자가 최대 9라는 점을 이용하면 좀 더 쉽게 풀 수 있다.

n이 k자리의 수라면, n - (9*k) ~ N 까지만 확인하면 된다.

 

구현 코드

#include<cstdio>

int N;

int main()
{
	scanf("%d", &N);

	int i = N, cnt = 0;

	while (i)
	{
		i /= 10;
		cnt++;
	}

	i = N - 9 * cnt;

	if (i < 0)
		i = 0;

	int sum, div;

	for (; i < N; i++)
	{
		sum = div = i;

		while (div)
		{
			sum += div % 10;
			div /= 10;
		}

		if (sum == N)
		{
			printf("%d", i);
			return 0;
		}
	}

	printf("0\n");
}

 

셀프 넘버

분해합과 유사하지만, 생성자를 찾는 것이 아니라 생성자가 존재하지 않는 셀프 넘버를 찾는 문제이다.

 

에라토스테네스의 체와 같은 방법으로

1. 초기에 모든 수를 셀프 넘버라고 가정한다.
2. 그리고 1~N까지 진행하면서, 해당 수의 분해합을 셀프 넘버가 아니라고 체크한다.
3. 그리고 최종적으로 셀프넘버인 수를 모두 출력한다.

 

구현 코드는 다음과 같다.

#include <cstdio>

const int MAX = 10001;

int d(int n)
{
	int sum = n;
	while (n > 0)
	{
		sum += n % 10, n /= 10;
	}
	return sum;
}

int main()
{
	bool selfNumbs[MAX + 35] = {};

	for (int i = 1, sum; i < MAX; ++i)
	{
		sum = d(i);
		selfNumbs[sum] = 1;
	}
	
	for (int i = 1; i < MAX; ++i)
	{
		if (!selfNumbs[i])
			printf("%d\n", i);
	}
}