[백준][C++] 4673: 셀프 넘버

문제

4673번: 셀프 넘버

풀이

구현, 브루트포스 알고리즘

 

1부터 10000까지의 수, n이 셀프 넘버인지 검사한다.

1. 1부터 n 사이의 수 i에 대해서 (n - i)가 n의 생성자인지 검사한다. 
2. (n - i)의 각 자리수의 합을 구한다. 
3. (n - i) + ((n - i)의 각 자기수의 합) == n 이라면 (n - i)는 n의 생성자이므로 셀프 넘버가 아니다.

위의 방법으로 셀프 넘버를 찾는다.

코드

#include <iostream>

using namespace std;

bool isSelfNumber(int n)
{
    bool out = true;

    // (n - i)가 n의 생성자라면 셀프 넘버가 아니다
    for (int i = 1; i < n; ++i)
    {
        int current = n - i;

        // current의 각 자리수를 더한다
        int current_sum = 0;
        int temp = current;
        while (temp != 0)
        {
            current_sum += (temp % 10);
            temp = temp / 10;
        }
        
        // (n - i) + ((n - i)의 각 자리수의 합)이 n이라면 i는 n의 생성자이다.
        if (current + current_sum == n)
        {
            out = false;
            break;
        }
    }

    return out;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    for (int i = 1; i <= 10'000; ++i)
    {
        if (isSelfNumber(i))
        {
            cout << i << '\n';
        }
    }

    return 0;
}