백준 2231번: 분해합 (C++)

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

2231번: 분해합

 

풀이

숫자가 주어졌을때 숫자 -> 분해합은 쉽지만 그 반대는 생성자가 여러개이기 때문에 완전 탐색을 통해 찾아야겠다고 생각했다.

 

우선, n을 인수로 받아 n-1까지 탐색하는 Generator 함수를 만들었다.

생성자는 n보다는 항상 작기 때문에 1부터 n-1번까지 탐색을 진행시켰다.

문자열로 변환해서 각 자리수를 더해가며 생성자를 찾는 알고리즘을 구성했는데

성공은 했지만, 다른 블로그를 찾아보니 tmp /= 10을 진행하며 구현한 방법이 더 쉬워보여서 살짝 아쉬웠다.

 

 

전체 코드

#include <iostream>
#include <string>

using namespace std;

int N;
string s;

int Generator(int n) {
	int tmp;
	for (int i = 1; i < n; i++) {
		tmp = i;
		s = to_string(i);
		for (int j = 0; j < s.size(); j++) tmp += s[j] - '0';
		if (tmp == n) return i;
	}
	return 0;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	cin >> N;

	cout << Generator(N);
}