분해합

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	192 MB	109250	50074	39400	45.235%

문제

어떤 자연수 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을 출력한다.

예제 입력 1

216

예제 출력 1

198

예제 입력 A

113

예제 출력 A

97

예제 입력 B

84164

예제 출력 B

84139

예제 입력 C

978

예제 출력 C

957

예제 입력 D

1

예제 출력 D

0

출처

ICPC > Regionals > Asia Pacific > Korea > Asia Regional – Seoul 2005 B번

• 데이터를 추가한 사람: kimtree97, lambda, minju1307, yjwr0528

알고리즘 분류

• 브루트포스 알고리즘

---

통과된 코드

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

string str = "";
int strToInt;

int tempInt, sum, result = 0;
string tempString;


int main()
{
	cin >> str; // 문자열로 입력을 받아놓는다.
	strToInt = stoi(str); // string => int

	// 입력값의 범위가 (1 ~ 1,000,000)이므로
	// M을 이루는 각 자리수의 합은 0이 될 수 없다.
	// 각 자리수의 합이 1 ~ N의 자리수 * 9 까지 모두 확인
	for (int i = 1; i <= str.length() * 9; i++) {
		
		sum = 0;

		tempInt = strToInt - i;

		tempString = to_string(tempInt);

		for (int j = 0; j < tempString.length(); j++) {
			sum += tempString[j] - '0'; // 모든 자리의 합
		}

		if (sum == i) { result = tempInt; } // 같은지 비교
	}

	cout << result;

	return 0;
}