백준 2231. 분해합 문제 풀이

백준 2231. 분해합 문제 풀이

"분해합"이라는 수학용어가 있습니다.
어떤 자연수 N을 N과 각 자릿수를 1의 자리로 하여 합산한 수를 분해합이라고 하는데요.

이를테면 123 이란 숫자의 분해합은 123 + 1 + 2 + 3 = 129가 됩니다.
이 때 반대로 123을 129의 생성자라고 합니다.

이번 문제는 129 입장에서 123과 같은 생성자를 구하는건데요.
주어지는 숫자는 최대 1,000,000까지 가장 작은 생성자를 구하는 겁니다.

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

2231번: 분해합

그냥 1부터 시작해서 주어지는 숫자까지 모든 경우의 수를 계산하다 첫번째 나오는 숫자를 구하면 되지 않나 할 수 있지만 2초의 시간제한이 있습니다.

사실 C++같은 경우 속도가 빨라서 2초 안에 대부분 구해지긴 할겁니다.
하지만 시간적으로 훨씬 효율적인 방법이 있습니다.

우선 주어지는 숫자가 123,456 이라고 쳐봅시다.

분해합은 생성자와 각 자릿수를 모두 더한 숫자인데,
각 자릿수를 모두 더한 수는 그렇게 큰 수가 아닙니다.

그러니까 123,456은 6자리 숫자이기 때문에
각 자릿수는 가장 커봐야 9 + 9 + 9 + 9 + 9 + 9 일겁니다.
즉 9 x 6자리 = 54라는 것이지요.
그렇다면 생성자는 123,456 - 54 보다 항상 크거나 같을 수 밖에 없습니다.
결국 123,402 부터 123,456 중에서만 생성자를 찾으면 되는 것이지요.

그럼 풀이 원리로 알아볼까요? 소스 해설보다는 알고리즘 설명입니다 :)

1번째. 먼저 주어지는 숫자의 자릿수를 구해야 합니다. 정수일 경우 해당하는 방법입니다.
숫자의 자릿수를 구하려면 해당 숫자를 10으로 반복해서 나눠주면서 몇번 나누면 0이 되는지를 구합니다.

123,456 의 경우 6번 10으로 나눠주면 되므로 6자리입니다.
123456(시작), 12345(1), 1234(2), 123(3), 12(4), 1(5), 0(6)

2번째. 검사를 시작할 수치를 구합니다. 자릿수에 따라 상이합니다.
256의 경우 3자리이므로  3에 각 1의 자릿수가 가질수 있는 최대값 9를 곱하면 3 x 9 = 27 가 되므로 검사를 시작할 수치는 229 가 됩니다.

3번째. 검사를 시작할 수치부터 주어진 수치까지 반복하면서 분해합이 주어진 수치와 동일한지 비교합니다.
첫번째 발견한 수치에서 중지합니다.
256의 경우 시작 수치 229 ~ 256 까지 검사합니다.

각 자릿수의 합계를 구하는 방법은 여러가지가 있지만
C++ 에서는 sprintf 명령문으로 문자열에 수치를 기록한 다음,
각 자리마다 수치를 더해주는 기법을 사용할 수 있어 속도가 매우 빠릅니다.

4번쨰. 3번째에서 조건에 맞는 수치를 발견했다면 해당 수치를 출력하고 종료합니다.
하지만 발견하지 못했다면 0을 출력하고 종료합니다.

---

위 알고리즘대로 반영된 소스입니다.
백준 사이트에서 돌려보면 소요시간이 0 ms 입니다 :)

#include <iostream>
#include <cstring>

using namespace std;

int main() {

	long n;
    std::cin >> n;
    // 숫자자릿수부터 계산
    long m = n;
    int digit = 0;
    while (m)
    {
        m /= 10;
        digit++;
    }
    // 분해합은 최소 n - 9*n의 자릿수 부터 시작
    long begin = n - digit * 9;
    char s[10];
    long sum = 0;
	bool find=false;
    for (long i = begin; i <= n; ++i)
    {
        sprintf(s, "%ld", i);
        sum = i;
		for(int j=0;j<strlen(s);++j)
			sum += s[j]-'0';
        if(sum == n )
		{
			find=true;
			cout << i << "\n";
			break;
		}
    }
	if(find==false)	cout << "0\n";

	return 0;
}