02.03. 분해합[Brute-force Search][백준 2231]

https://www.acmicpc.net/problem/2231

2231번: 분해합

Algorithm classification : Brute-force Search

02.03.1. Problem

When there is a certain natural number N, the decomposition sum of the natural number N means the sum of N and each digit constituting N. If the decomposition sum of any natural number M is N, then M is said to be a generator of N. For example, the decomposition sum of 245 becomes 256 (=245+2+4+5). So 245 is a constructor of 256. Of course, some natural numbers may have no constructors. Conversely, there can be natural numbers with multiple constructors. Write a program to find the smallest constructor of N given a natural number N.

 

02.03.2. Input limit

The first line is given a natural number N (1 ≤ N ≤ 1,000,000).

 

02.03.3. Output

Print the answer on the first line. If there is no constructor, 0 is output.

 

02.03.4. Solution

N의 분해합은 반드시 N보다 크다는 것을 생각하시면 됩니다.

	for(i = 1; i <= n; i++){
		temp = m = i;
		while(temp){
			m += (temp%10);
			temp /= 10;
		}
		if(data[m] == 0){
			data[m] = i;	
		}
	}
	
	printf("%d", data[n]);

indexing만 어떻게 잘하면 될 듯합니다. 적절하게 index를 활용해주는 센스만 있다면 낮은 공간복잡도를 제공할 수 있을 것입니다.