#2231. 분해합

문제링크

Problem

• 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합
• 245의 분해합 : 245+2+4+5 = 256
  245는 256의 생성자
• 생성자는 없을 수도 여러 개일 수도 있음
  • 없다면 0 출력

Goal: N이 주어졌을 때 N의 가장 작은 생성자 출력

Solution

• 1부터 최대 N-1까지 분해합을 구하면서 풀어보면 어떻게 될까?
• 1부터 분해합을 구하다가 N이 되었을 때 종료하면 가장 작은 생성자를 출력할 수 있다.
• 분해합 구하기

  212의 분해합 구하기
  212  자릿수 3
  // #1.
  212 / 10^2 = 2 -> 212+2
  212 - 2*10^2 = 12
  // #2.
  12 / 10^1 = 1 -> 212+2+1
  12 - 1*10^1 = 2 -> 212+2+1+2
  
  11의 분해합 구하기
  11 자릿수 2
  div = 10 (10의 제곱 수)
  sum = 11 (분해합)
  // #1.
  temp = 11 / 10 = 1 (계산 용도)
  num = 11 - 10 = 1
  sum = 11 + 1 = 12
  div = 1
  // #2.
  temp = 1 / 1 = 1
  num = 1 - 1 = 0
  sum = 12 + 1 = 13
  div = 0
  
  그냥 더 간단한 방법이 생각났다. (2 Try 참고)
  sum, temp = 11
  sum = 11 + 11 % 10
  temp = 11 / 10 = 1
  sum = 12 + 1 % 10 = 13
  즉, 
  sum += temp % 10
  temp /= 10

1 Try

#include <iostream>
#include <cmath>
using namespace std;
// 자릿 수 체크
int getLength(int num) {
	int count = 0;
	do {
		count++;
	}while(num/=10);
	return count;
}
// 분해합 게산 
int distributeSum(int num) {
	int length = getLength(num);
	int div = pow(10, length-1);
	int sum = num; int temp;
	for(int i = 0; i < length; ++i) {
		temp = num / div; 
		num = num - temp * div; 
		sum += temp; 
		div /= 10;
	}
	return sum;
}
int main()
{
	int n, i;
	cin >> n;
	for(i = 1; i < n; ++i) {
		if(n == distributeSum(i)) {
			cout << i << '\n';
			break;
		}
	}
	if(i == n) cout << 0 << '\n';
	return 0;
}

108ms

2 Try

#include <iostream>
using namespace std;
int distributeSum(int num) {
	int sum, temp;
	sum = temp = num;
	do {
		sum += temp % 10;
	}while(temp /= 10);
	return sum;
}
int main() {
	int n, i;
	cin >> n;
	for(i = 1; i < n; ++i) {
		if(n == distributeSum(i)) {
			cout << i << '\n';
			break;
		}
	}
	if(i == n) cout << 0 << '\n';	
	return 0;
}

8ms