[백준] 2231 분해합

문제링크] https://www.acmicpc.net/problem/2231

2231번: 분해합

---

문제요약

예를 들어 설명하면 198은 198+1+9+8 = 216 입니다. 여기서 198을 216의 생성자라고 합니다. 이 문제는 숫자 N이 주어졌을 때 생성자 M을 구하는 문제입니다.

풀이

백준의 단계별로 풀어보기에서 '브루트 포스' 단계에 있는 문제입니다. 브루트 포스란 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 문제를 푸는 것입니다. 모든 경우의 수를 찾기 때문에 동작하는 데 오랜 시간이 걸리지만 정확한 결과를 도출할 수 있는 알고리즘입니다. 하지만 경우의 수가 너무 많은 경우 몇 년이 걸려도 답을 못 찾을 수 도 있습니다. 

 

그럼 문제 풀이를 해보겠습니다. 우선 입력받은 숫자가 몇 자리 수 인지 알기 위해서 degree를 설정해 주었습니다.

 

for 반복의 시작은 주어진 숫자보다 한 차수 낮은 자리부터 시작해야합 니다. 예를 들어 10이 주어줬을 때, 가장작은 생성자는 5이임으로 십의 자리보다 낮은 일의 자리부터 for 문을 돌아주어야 답을 찾을 수 있습니다.

 

안 쪽 for문에서는 자연수 k 와 k의 모든 자리수를 더해주는 연산을 처리해주었습니다.

 

만약에 k 와 k의 모든 자리수를 더한 값과 주어진 수가 같을 경우 k를 리턴해줍니다.

 

반복문은 k가 주어진 수 num 과 같아질 때까지 반복해줍니다. 반복문 리턴없이 빠졌나왔다는 것은 생성자가 존재하지 않는 것이므로 0을 리턴해줍니다.

---

c/c++ 코드로 작성하였습니다.

#include <iostream>
#include <math.h>

using namespace std;

int DecompositionSum(int num) {
	int degree = 0;
	int result;

	int compare = num;
	while (compare >= 10) {
		compare /= 10;
		degree++;
	}

	int start = (int)pow(10, degree-1);

	for (int k = start; k <= num; k++) {
		result = k;
		int add = k;
		for (int i = degree; i >= 0; i--) {
			int degree_num = (int)pow(10, i);
			result += add / degree_num;
			add %= degree_num;
		}

		if (num == result) return k;
	}

	return 0;
}


int main() {
	int num;
	cin >> num;

	printf("%d", DecompositionSum(num));


	return 0;
}