[백준 2231번][C++] 분해합

<문제 소개>

---

<소스 코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{	
	int result = 0;

	int N;
	cin >> N;
	if (N < 1 || N > 1000000) return 0;

	for (int i = 1; i < N; i++)
	{
		int sum = i; // 분해합
		int curNum = i; // 더해야할 숫자

		while (curNum > 0)
		{
			sum += curNum % 10; // 1의 자리의 숫자를 저장
			curNum /= 10; // 1의 자리 숫자를 없앰
		}

		if (sum == N)
		{
			result = i; // 분해합이 입력값 N과 같은 경우 해당 생성자 i를 result에 담고 반복문을 끝낸다.
			break;
		}
	}

	cout << result;

	return 0;
}

---

<풀이과정>

1. 숫자를 입력받음

2. 1이상 N미만을 반복하며 해당 수와 해당 수의 자릿수들을 각각 더해서 주어진 수와 같은지 판단

3. 맞다면 해당 숫자를 출력하고, 아닌 경우 반복을 계속 진행한다.

4. 반복이 끝날때까지 분해합의 생성자가 나오지 않을경우 0을 출력한다.

---

 

<코멘트>

 

조금 어려워서 시간이 걸렸다,,🤔

일의 자리숫자의 분해합을 구하는 게 헷갈렸다.

 

예외처리되는 경우를 알아보다가 다른 분들의 풀이를 보다가 자릿수를 이용하여 시간을 엄청 단축한 풀이가 있었는데

내용은 아래와 같았다.

각 자리의 숫자는 9까지밖에 안되고, 숫자의 범위가 6자릿수 이내이므로

분해합을 구할때 더해지는 최대값이 9+9+9+9+9+9 = 54가 된다.

그러므로 for문을 돌때 N - 54 번째부터 시작하면 된다. 

아래 사진은 밑부분이 내 풀이의 풀이시간이고, 윗부분이 이 풀이로 풀었을 때 나온 풀이시간이다.(0ms ㄷ.ㄷ)

---

<추가 소스코드>

#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;

int main()
{	
	int result = 0;

	int N;
	cin >> N;
	if (N < 1 || N > 1000000) return 0;

	int digit = 0; // 자릿수
	int temp = N;

	while (temp > 0)
	{
		temp /= 10;
		digit++; // 자릿수 증가
	}

	for (int i = N - digit * 9; i < N; i++)
	{
		int sum = i; // 분해합
		int curNum = i; // 더해야할 숫자

		while (curNum > 0)
		{
			sum += curNum % 10; // 1의 자리의 숫자를 저장
			curNum /= 10; // 1의 자리 숫자를 없앰
		}

		if (sum == N)
		{
			result = i; // 분해합이 입력값 N과 같은 경우 해당 생성자 i를 result에 담고 반복문을 끝낸다.
			break;
		}
	}

	cout << result;

	return 0;
}