백준 2231 - 분해합

문제 번호: 2231

문제 제목: 분해합

문제 주소: https://www.acmicpc.net/problem/2231

문제 내용

분해합은 숫자 i에 i의 각 자리 수를 모두 합한 값을 의미한다. i를 분해합하여 N이 나오는 경우 i는 N의 생성자라 한다.
입력된 수 N의 생성자를 출력한다.

테스트 케이스

1	0
2	1
216	198
999999	999954
1000000	0

문제 풀이

브루트 포스로 푸는 문제지만, 1부터 시작하는건 매우 비효율적이므로 범위를 어느 정도 좁힐 필요가 있다.
생성자 수 + 생성자의 각 숫자를 모두 합해서 N이 나와야 하므로 (N - 자리수 * 9) ~ (N - 1) 이 탐색 범위가 된다.
10 이하인 수는 짝수에게만 생성자가 있으므로 그에 맞춰 코드를 작성하면 된다.

풀이 코드

#include <iostream>
using namespace std;

void BAEKJOON_2231()
{
	int N;
	cin >> N;
	int M = 0;
	if (N <= 10)
	{
		M = N % 2 == 0 ? N / 2 : 0;
	}
	else
	{
		int digit = 0;
		int copyN = N;
		while (copyN)
		{
			digit++;
			copyN /= 10;
		}
		for (int i = N - digit * 9; i < N; i++)
		{
			int currentNumber = i;
			int sum = i;
			while (currentNumber)
			{
				sum += currentNumber % 10;
				currentNumber /= 10;
			}
			if (sum == N)
			{
				M = i;
				break;
			}
		}
	}
	cout << M << endl;
	return;
}