백준 2231번: 분해합

 

---

 

문제

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

 

 

 

 

실행 결과

 

 

 

코드(c++)

#include <iostream>
#include <string>
using namespace std;

int main() {
	int n;
	cin >> n;
	int result = 0;

	for (int i = 1; i < n; i++) {
		int sum = i;  // 분해합
		int temp = i;  // 자릿수 합 용

		while (sum > 0) {
			/* 자릿수별로 더하기 */
			sum += temp % 10;
			temp /= 10;
			if (temp == 0) break;
		}

		if (sum == n) {
			/* 입력받은 n과 일치되면 for 문 종료 */
			result = i;
			break;
		}
	}
	
	cout << result;
	return 0;
}

 

 

 

 

코드 설명

1. 사용자로부터 정수 n을 입력받는다.
2. 반복문을 돌면서 현재 숫자 i와 그 숫자의 각 자릿수를 더하여 그 결과를 sum에 저장한다.
3. 만약 sum이 입력받은 n과 같아지면, 현재 숫자 i가 n의 생성자이다.

 

이 문제를 해결하기 위해서는 분해합 및 생성자의 개념을 정확하게 알고 있어야 한다.

생성자란 자기 자신과 자신의 각 자릿수를 더해서 원래의 수를 만들 수 있는 수이다.

 

생성자는 어떤 숫자와 그 숫자의 각 자리수를 더해서 특정한 '분해합'을 생성할 수 있는 수이다.

분해합은 어떤 숫자와 그 숫자의 각 자리수를 모두 더한 결과 값이다.

 

예를 들어, 245의 분해합은 256(=245+2+4+5)이 된다. 245는 256의 생성자가 된다. 

 

for문을 통해 1씩 키우면서 분해합을 만드는 생성자를 찾고,

그 내부 while 문 내에서 자릿수를 더하면서 입력값과 일치하는 순간 생성자를 구할수 있다.

 

 

---

 

문제 출처:

2231번: 분해합