[2231] 분해합

브론즈 2

브루트 포스 알고리즘(Brute Force) : 완전 탐색. 가능한 모든 경우의 수 탐색

 

<개념 정리>

N의 분해합 : N + (N을 이루는 각 자리수의 합)

N : M의 분해합
M : N의 생성자

 

생성자 + 각 자리 수의 합 = N(분해합)이 되면 된다

입력으로 분해합이 들어오므로 그에 따른 생성자를 구하면 된다

근데 이렇게 구한 생성자 중에서도 제일 작은 생성자를 구해야하므로 if문으로 조건을 걸어주었다

bool 자료형을 이용하여 생성자가 없는 경우도 처리해주었다

각 자리 수의 합을 구할 때에는 자연수의 범위가 1,000,000(100만) 이하이므로 그에 맞게 설정해주었다

i의 나머지를 10의 @제곱으로 나누면 자릿수가 나온다

#include <iostream>
using namespace std;

int N; int sum;
int minimum = 1000001;
bool isit = false;

int main() {
	cin >> N;

	// 생성자 + 각 자리 수 = N
	for (int i = 1; i <= N; i++) {
		sum += i; // 생성자
		sum += (i / 1000000) + 
			((i % 1000000) / 100000) + 
			((i % 100000) / 10000) + 
			((i % 10000) / 1000) + 
			((i % 1000) / 100) + 
			((i % 100) / 10) + 
			(i % 10); // 각 자리 수의 합
		// 구한 분해합과 같고 가장 작은 생성자를 구해야하므로
		if ((sum == N) && (i < minimum)) { isit = true; minimum = i; }
		sum = 0;
	}
	if (isit == true)	cout << minimum;
	else cout << 0; // 생성자가 없는 경우
}