[BOJ] 백준_2231번_분해합_C/C++

문제 출처

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을 출력한다.

 

틀린 코드

//[BOJ]_2231번_분해합_틀린코드
#include <iostream>
using namespace std;
int main()
{
	int n;
	int tot = 10;
	int a, b, c, d, e, f;

	cin >> n;

	while (true)
	{
		a = tot / 100000;															//10만의 자리 수
		b = (tot - a * 100000) / 10000;											//만의 자리 수
		c = (tot - a * 100000 - b * 10000) / 1000;							//천의 자리 수
		d = (tot - a * 100000 - b * 10000 - c * 1000) / 100;				//백의 자리 수
		e = (tot - a * 100000 - b * 10000 - c * 1000 - d * 100) / 10;	//십의 자리 수
		f = tot % 10;																//일의 자리 수

		if (tot > n)
		{
			cout << "0" << endl;
			break;
		}
		else if ((tot < 100) && (n == tot + e + f))
		{
			cout << tot << endl;
			break;
		}
		else if ((tot < 1000) && (n == tot + d + e + f))
		{
			cout << tot << endl;
			break;
		}
		else if ((tot < 10000) && (n == tot + c + d + e + f))
		{
			cout << tot << endl;
			break;
		}
		else if ((tot < 100000) && (n == tot + b + c + d + e + f))
		{
			cout << tot << endl;
			break;
		}
		else if ((tot < 1000000) && (n == tot + a + b + c + d + e + f))
		{
			cout << tot << endl;
			break;
		}
		tot++;
	}
	return 0;
}

생각나는대로 풀어봤더니 사실 다 쓰고 나서도 너무 대책없어보이는 코드였다. Visual Studio에서 실행시켜보면 답이 잘 출력되기는 하나 백준에서는 왠지 모르게 "틀렸습니다" 한 마디로 자세히 틀린 이유를 알려주지 않았다.

---

 

코드

// [BOJ]_2231번_분해합
#include <iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int i = n;
	int cnt=0;
	while (i)
	{
		i /= 10;
		cnt++;
	}

	int tot = n - 9 * cnt;
	int num = tot;

	while (true)
	{

		int sum = 0;
		sum += num;
		int x = num;
		while (x)
		{
			sum += (x % 10);
			x /= 10;
		}

		if (num == n) {
			cout << "0" << endl;
			break;
		}

		if (sum == n) {
			cout << num << endl;
			break;
		}
		else
			num++;
	}
	return 0;
}

 

풀이 과정

먼저 cnt에 입력받은 수 n의 자리수를 구한다. 그 후 생성자가 될 만한 수를 구하는데 우선 생성자는 n에서 각각 자릿수의 최댓값인 9에 자릿수인 cnt를 곱한 값을 뺀 n-9*cnt부터 시작해서 검사하도록 했다. 예를 들어 1234라는 숫자를 입력받았을 경우 분해합이 1234가 되려면 생성자는 생성자와 각 자릿수를 더한 값이 1234가 되어야 하기에 1234보다 각 자리의 최대 수인 9를 4번 뺀 값부터 시작할 것이라는 이야기이다. 시작검사값을 num으로 넘긴 후 검사를 시작했다. num값은 이후 쭉 검사해서 n에 도달했을 때까지 생성자를 발견하지 못했을 경우를 고려하기 위해 살려두고 x에 저장해서 사용하였다. sum에 num값을 우선 더한다. num값을 넘겨받은 x가 0이 될때까지 sum에 x를 10으로 나눈 나머지값을 더하고 x를 10으로 나눈 몫 값으로 저장한다. 10으로 계속 나누다보면 그 몫은 0이 될 것이고 그 때 sum에는 초기 num값과 각각의 자리수를 더한 값이 저장된다. num을 하나씩 더해보면서 이 sum값이 처음에 입력받은 n와 같은지만 비교하면 된다. num이 n과 같은 값이 될 때까지 sum값이 n과 같지 않을 경우 생성자가 없는 경우이므로 0을 출력한다. 

---