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

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

---

풀이

Algorithm

• 문제 이해
  • 1부터 N까지 수를 탐색하여 분해합을 구하고, 그것이 N이 되는 수를 찾아내면 된다.
• 변수 설명
  • N : 문제에서 설명하는 N 값을 저장한다.
  • M : 생성자를 구하기 위해 쓰이는 변수이다. / 1부터 N까지의 수를 탐색한다. / 초깃값은 1이다. M=1; / 수를 1씩 증가시키며 그 수의 분해합이 N이 되는지 살펴본다.
  • temp : M의 분해합을 구하기 위해 쓰이는 변수이다. / M의 자릿수를 하나씩 읽어올 때 쓰인다.
  • sum : M의 분해합을 저장하는 변수이다. / 먼저 M을 더해준 후, M의 자릿수를 하나씩 읽어와서 더해주는 방식으로 M의 분해합을 저장한다. / M 값이 바뀔 때마다 sum도 0으로 초기화 해주어야 한다.
• 전체적인 알고리즘 설명
  • M을 1로, sum을 0으로 초기화해준 후, N을 입력받아 온다.
  • while문을 돌면서 M을 1부터 하나씩 증가시키며 M이 N의 생성자인지 검사를 한다. M이 N의 생성자가 되는 순간 루프를 빠져나와 찾은 생성자 값을 출력해준다.
  • sum이 N과 같아지면 N의 생성자를 찾은 것이고, 또 M이 N보다 크거나 같은 경우는 없으므로, 이 때를 고려하여 while문의 조건을 설정해준다. // sum!=N && M<N
  • sum과 temp를 모두 M으로 설정해준다.
  • 그 후 while문을 통해 M의 각 자릿수를 더하는 과정을 실행한다.

		// 각 자릿수를 더함
		while (temp != 0) {
			sum += temp % 10;
			temp /= 10;
		}

• 
  
  • temp의 끝자리 수를 읽어오고 (temp%10) sum에 더해준다, 그 후 temp에 10으로 나눈 몫을 저장하며 이 과정을 반복하면 M의 각 자릿수를 모두 sum에 더해줄 수 있다.
  • 예를 들면 M = 123인 경우, temp%10 = 3으로 먼저 3을 더해준 후, temp/=10을 하여 temp 값은 12가 된다. 또 이제 temp%10 = 2가 되어 2를 더한 후, temp/=10을 하여 temp 값은 1이 되고, 이후 temp의 끝자리 수는 1이 되어 1을 더해준 후 temp/=10 값은 0이 되어 while문을 빠져나오게 된다.
  • 이 과정 후 M++을 하여 이 과정을 계속 반복한다.
  • 루프를 빠져나온 후에 만약, M==N이라면, 생성자를 찾지 못한 것이므로 0을 출력해준다.
  • 그렇지 않다면 M-1을 출력한다.
  • 여기에서 M-1을 출력하는 이유는, 루프 마지막에 M++;로 인해 찾은 생성자보다 1 큰 값이 되어 루프를 빠져나오기 때문이다.

code

#include <iostream>
#include <string>
using namespace std;
int main() {
	int N, M = 1, temp, sum = 0;
	cin >> N;
	while (sum != N && M < N) {
		// 생성자 찾거나, M이 N과 같아질 때 루프를 빠져나옴
		sum = M;
		temp = M;
		// 각 자릿수를 더함
		while (temp != 0) {
			sum += temp % 10;
			temp /= 10;
		}
		M++;
	}
	if (M == N) cout << 0 << '\n';
	else cout << M-1 << '\n';
	return 0;
}