분해합
대표적인 완전탐색 문제이다. 컴퓨터의 입장에서 n번 정도의 연산은 간단한 일이다. 이를 명심하자.
이 문제는 주어진 N에서 생성자를 찾아내려고 하면 매우 어려워진다.. (어떻게 해야할 지 아직 잘 모르겠다..)
그럼 어떻게??
생성자는 무조건 주어진 분해합 N보다는 작다. 따라서 1부터 N까지 가면서 분해합 N을 만들어 내는 생성자를 발견하면 이를 출력하고 종료하면 된다.
코드보기
#include <cstdio>
int main() {
int n;
scanf("%d", &n);
for(int i=1; i<n; i++) {
int dsum = 0;
int inum = i;
do {
dsum += inum % 10;
inum /= 10;
} while (inum != 0);
if ((i + dsum) == n) {
printf("%d\n", i);
return 0;
}
}
printf("%d\n", 0);
return 0;
}
방법2. 분해합을 만들어 주는 함수를 만들면 한결 간단해진다.
#include <cstdio>
int decompSum(int n) {
if (n == 0) { return 0; }
return n%10 + decompSum(n/10);
}
int main() {
int n;
scanf("%d", &n);
for(int i = 1; i<n; i++) {
if (i + decompSum(i) == n) {
printf("%d\n", i);
return 0;
}
}
printf("%d", 0);
return 0;
}