[BOJ/백준 2231][C++] 분해합

문제

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

 

문제 내용

자연수 N을 입력받아, N의 가장 작은 생성자를 구하는 문제이다.
즉, 우리의 결과값의 분해합을 구하였을 때 N이 만들어지면 된다.

 

문제 풀이

이 문제의 경우, 완전탐색 알고리즘(brute force)을 사용하여 문제를 해결했다.

이 문제의 결과값은 항상 1 이상, N 미만이다. (생성자가 없는 경우는 0)
따라서 for 반목문을 1~N-1까지 돌면서 각 숫자의 분해합을 구해보면 된다.

만들어진 분해합이 N과 같으면 종료하면 되고, for문이 끝날 때까지 결과가 나오지 않는다면 생성자가 없는 경우이므로 0을 출력하면 된다.

특정 숫자의 분해합을 구하는 과정은 while문을 통해 구현했다.
10으로 나누었을 때의 나머지를 차례로 더하면 된다.

즉, 245라는 숫자의 분해합을 구하려면, 245+5(일의 자리)+4(십의 자리)+2(백의 자리) =256 이 된다.

 

코드

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    
	//입력
	int num;
	cin >> num;

	//문제 해결
	for (int i = 1; i < num; i++) {
		int tmp = i;
		int sum = i;

		while (tmp != 0) {
			sum += tmp % 10; // 1의 자리 더하기
			tmp /= 10;
		}

		if (sum == num) {
			cout << i << '\n';
			return 0;
		}
	}

	cout << 0 << '\n';
	return 0;
}

 

문제 코드 설명

1) 문제 해결

for 반복문을 1~N-1까지 돌며 분해합을 구한다.
while 반목문을 통해 특정 수의 분해합을 구하는 과정을 진행한다.
while 반복문을 빠져나오고 나서 N과 비교하는 과정을 거친다.