Boj 2231 C++ 분해합

어떤 수의 분해합이란 그 숫자를 이루는 각자리 숫자의 합과 그 숫자를 합한 값이다.

어떤 숫자 M의 분해합은 N이면 M은 N의 생성자이다. 이때. 숫자 N(1<=N<=1000000)

이 주어졌을 때 N의 최소 생성자를 구해내는 알고리즘이다.

#include<iostream>

using namespace std;

int main() {

    int N, i, number;

    cin>>N;


    for(i = 0; i < N; i++) {

        int sum = 0;
        number = i;
        while(number > 0) {
           sum = sum + number % 10;
            number = number / 10;
        }
        sum = sum + i;

        if(sum == N) {
            cout<<i;
            return 0;
        }

    }
     
     cout<<"0";


}

이문제의 태그는 브루트포스 알고리즘이였다.

*브루트포스 알고리즘이란?

구해야 하는 모든 범위를 탐색하는 알고리즘으로, 시간이 많이 소요되지만 반드시 정답을 찾아낸다.

brute==무식하다 

brute force-->무식하게 구하는 것

 

우선은 숫자 N을 입력받은 후, 0부터 N-1까지의 숫자에 대한 연산을 진행한다. 각자리 숫자의 합을 구한다. 이때, sum은 반복문 안에서 선언하여 중복 오류가 발생하는 것을 막는다. 그 다음에는 각자리 숫자의 합에 그 숫자를 더한다. 이때, 마지막 결과가 N과 일치하면, 그 숫자는 N의 생성자가 되기 때문에 그 숫자를 출력한다(최소생성자)-->(각 자리 숫자와 그 숫자 자체를 더했을 때 N이 되는 값)

 

하지만 루프가 모두 끝날 때 까지 N과 일치하지 않으면, N의 최소 생성자는 존재하지 않으므로 0을 출력한다.

 

이때, 두 케이스는 return 0;을 기준으로 구분할 수 있다