[Baekjoon] 2231번: 분해합

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

2231번: 분해합

 

---

 

문제 해결 과정

착안

주어지는 자연수 \(N\)에 대하여, 문제에서 정의되어있는 분해합이 \(N\)이 되는 수들 중에서 가장 작은 값을 출력하는 문제인데 분해합의 값이 \(N\)이 되는 숫자를 찾는 마땅한 방법이 없으므로 낮은 수부터 시작하여 직접 분해합을 구해보며(브루트 포스 알고리즘) 그 값이 \(N\)이 되는 값이 있는지 살펴보고자 하였다.

 

단, 이때 어떤 미지의 수 \(n\)의 분해합이 \(N\)이 되기 위해서는 (문제에서 주어진 정의에 의하여) 아래와 같은 조건을 반드시 만족해야하므로 분해합이 \(N\)이 될 가능성이 있는 숫자들에 대해서만 계산함으로써 계산량을 줄일 수 있을 것이라고 판단하였다.

 

• \(n\)의 분해합이 \(N\)이면, 반드시 \(n < N\) 이다.
• \(n\)의 분해합이 \(N\)이고 \(N\)이 \(k\) 자리의 수일 때, \(N - 9k \leq n\) 이다.

 

구현

따라서, 우선 분해합을 계산하기 위한 함수를 하나 정의하고 테스트한 뒤 \(N - 9k \leq n < N\)을 만족하는 수들에 대해서만 분해합을 계산하여 \(N\)과 같은지 비교하였다. 자리수마다의 숫자들의 합을 편리하게 구하기 위해서 분해합을 구하는 함수에서는 인수로 받은 자연수를 문자열 형태로 바꾸는 트릭을 사용하였다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int DecomposeSum(int num)
{
	int sum = num;
	char str[7] = { 0, };
	sprintf(str, "%d", num);

	int i = 0;
	while (str[i])
		sum += (str[i++] - '0');

	return sum;
}

int main()
{
	char str[7] = { 0, };
	scanf("%s", str);

	int N = atoi(str);
	int min = N - 9 * (int)strlen(str);
	min = min ? min : 1;

	while (min < N)
	{
		if (DecomposeSum(min) == N)
		{
			printf("%d\n", min);
			break;
		}

		min++;
	}
	
	if (min == N)	printf("0\n");

	return 0;
}

 

실행 결과

아래 결과: 1부터 분해합을 일일이 계산한 결과(테스트/비교 목적), 위 결과: 연산량을 줄여 실행한 결과.