[백준 알고리즘][완전탐색] 223번 분해합

문제 정의 

어떤 자연수 N이 있을 때, 그 자연수의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들면 245의 분해합은 245+2+4+5=256이되고, 256의 생성자는 245가 된다. N이 주어졌을 때 가장 작은 생성자를 구해내는 프로그램을 작성해야한다. 

문제 출처: 백준 온라인 저지(https://www.acmicpc.net/problem/2231)

문제 풀이

어떤 수를 분해시켜 N과 N을 이루는 각 자리수의 합을 계산했을 때, 입력한 숫자가 나와야하고 그 어떤 수 중에서 가장 작은 수를 구해야한다. 만약 주어진 자연수 N을 만들기 위해서 모든 수를 다 분해합 시킨다고 생각하면, 1,000,000을 만들기 위해서는 약 999,000 대의 숫자에서 주어진 자연수의 생성자를 찾아야한다. 이 정도의 수면 큰 수인가? 일단 시간 제한이 2초니까 무식하게 모든 분해합을 만들어보는 코드로 작성해본다. 

분해합을 만들기 위해 생각해봐야하는 부분은 숫자가 들어왔을 때 각 자리수를 어떻게 나눌 것인지 이다. 만약 123이 들어오면 1+2+3+123이 되도록 해야하는데 몇자리수가 들어올지 모르니 일단 들어오는 수를 10으로 계속 나눈다. 그리고 나누면서 나머지는 각 자리의 합으로 더한다. 123/10->12가 되면서 3더하기 12/10 ->1이 되면서 2더하기 1/10->1보다 작을 경우 반복문이 종료되게한다.

*한번에 반복문 조건 클리어해서 풀었다.

코드

#include<stdio.h>

int N;

void main()

{

int i, j;

int result = 0;

scanf("%d", &N);

for(i=1; i<=N; i++)

{

j = i;

result = 0;

while( j/10 != 0)

{

result += j%10; 

j = j/10;

}

result += j;

result = result + i;

if(result == N)

break;

if(i==N){

i=0; 

break;

}

}

printf("%d\n", i);

}