[백준/BOJ] 2231번 분해합 (C/C++)

백준 온라인 저지(BOJ) 2231번 분해합
https://www.acmicpc.net/problem/2231

2231번: 분해합

* 사용언어 : C언어, C++

 

1. 문제

어떤 자연수 N에 대해 N과 N의 각 자리수의 합을 분해합이라 함
어떤 자연수 M의 분해합이 N인 경우 M을 N의 생성자라 함
자연수 N에 대해 가장 작은 생성자를 출력 (없으면 0)

 

2. 풀이

문제 이해를 위해 생성자는 무시하고 우선 분해합만 생각해보겠습니다.

분해합이 뭔지 직관적으로 와닿지가 않아서
아래와 같이 숫자 하나하나 분해합을 계산해봤습니다.
 
1 의 분해합은 1 + 1 = 2
2 의 분해합은 2 + 2 = 4
...
10 의 분해합은 10 + 1 + 0 = 11
11 의 분해합은 11 + 1 + 1 = 14
...
245 의 분해합은 245 + 2 + 4 + 5 = 256 (문제 예시)
...
 
분해합 계산을 통해 분해합의 개념을 얼추 잡을 수 있게 됐습니다.
 

생성자는 분해합과 반대되는 개념이라고 보면 되는데,
위 예시에서 14의 생성자는 11입니다.
(11의 분배합은 14이고, 14의 생성자는 11)
 
입력 N의 생성자를 찾기 위해 N부터 1씩 줄여나가면서 탐색을 하면 빠르겠지만,
문제에도 주어졌듯이 생성자가 여러 개인 경우가 있기 때문에
반드시 작은 수 부터 오름차순으로 확인해야 합니다.
 
예를 들어 208의 생성자는 194, 203로 2개 입니다.
(194 + 1 + 9 + 4 = 208, 203 + 2 + 0 + 3 = 208)
 
코드는 n을 입력받은 후,
1부터 n까지 탐색하면서 부분합이 n이 되면 반복문을 탈출하도록 구현했습니다.
만약 반복문을 탈출했다면 (즉 res == N), 생성자(i)를 출력하고, 아니면 0을 출력해줍니다.
 
생상자가 부분합과 꽤 인접한 값이라는 것을 활용하여 코드를 더 효율화할 수 있겠지만,

최적화를 통해 더 얻을 것이 없는 문제 같아서 진행하지 않고 마쳤습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
2231_분해합
1112KB	8ms
*/
#include <cstdio>

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	int n, m, res;
	scanf("%d", &n);

	int i;
	for (i = 1; i <= n; ++i) {
		res = m = i;
		while (m) {
			res += (m % 10);
			m /= 10;
		}

		if (res == n) break;
	}

	printf("%d\n", res == n ? i : 0);
	return 0;
}