[C언어] 백준 2231번

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

2231번: 분해합

 

문제

어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 따라서 245는 256의 생성자가 된다. 물론, 어떤 자연수의 경우에는 생성자가 없을 수도 있다. 반대로, 생성자가 여러 개인 자연수도 있을 수 있다.

자연수 N이 주어졌을 때, N의 가장 작은 생성자를 구해내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

 

출력

첫째 줄에 답을 출력한다. 생성자가 없는 경우에는 0을 출력한다.

 

 

 

---

 

#include <stdio.h>
 
int main() {
    int n;
	scanf("%d", &n);
 	
	for (int i = 1; i < n; i++) {
		int constructor = i; // constructor: 생성자
	
		// 각 자리 수를 구하고 더해 생성자를 만든다.
		int num = i; // num: 각 자리 수 
		
		while(num > 0) {
			constructor += num % 10;
			num /= 10;
		}
		
		// 생성자가 n가 같다면 생성자를 출력한다. 
		if (constructor == n) {
			printf("%d", i);
			n = 0;
			break;
		}
	}
	
	// 생성자가 없다면 0을 출력한다. 
	if (n != 0) {
		printf("0");
	}
}

 

 

문제 해결 과정

 일단 문제에서 생성자의 정의부터 읽어보았다. 생성자는 어떤 자연수 M의 분해합(M + M의 각 자리 수의 합)이 N인 경우, M을 N의 생성자라고 한다. 즉, 입력한 수와 어떤 수의 분해합이 같은 것이 있으면 생성자가 있다고 할 수 있다. 따라서 생성자가 없을 수도 있고 1개 혹은 여러 개가 될 수도 있다. 어떤 숫자의 분해합을 구해야 입력한 수와 같게 되는 숫자가 있는지 예상은 하지 못한다. 하지만 한 가지 확실한 것은 생성자는 어떤 자연수 M + M의 각 자리 수의 합이 입력한 수와 같아야 하므로 절대 입력한 수를 넘어가지는 않는다. 그리고 생성자가 여러 개면 가장 작은 수를 출력한다는 것이다. 따라서 1부터 입력한 수까지 반복문을 통해 탐색을 하면서 찾아나가는 방법을 선택하였다. 

 

 반복문 안에는 생성자를 구할 변수를 선언하여 변수 i의 분해합을 구하는 수식을 작성하였다. 각 자리 수의 합은 i를 10으로 나눈 나머지와 10으로 나눈 몫을 다시 반복하는 방식으로 한 자리씩 구해 더하여 생성자 변수에 대입했다. 그 생성자 변수가 입력한 수와 같다면 그 숫자는 입력한 수의 생성자가 되므로 i를 출력하였다. 하지만 다르다면, 생성자가 없으므로 0을 출력하도록 하였다.