[BOJ] 4673번: 셀프 넘버

링크 : https://www.acmicpc.net/problem/4673

독해력이 딸려서 그런지... 사실 처음에 보고 이해를 못했다. 그러니 당연히 코드를 못 짰는데 어쨌든 d(N)은 N의 각 자릿수 합 + N이고 n을 d(n)의 생성자라고 한다.

33은 39의 생성자가 될 수 있는 건데 생성자들이 없는 수가 셀프 넘버다.

1, 3, 5, 7 ... 같은 수들인데 어떤 n으로도 d(n) = 1, 3, 5, 7 ... 을 만들어 낼 수 없다는 말이다. 

그래서 난 10,000까지 반복문을 돌리면서 d(i)값을 배열 인덱스에 넣어줬다. (배열의 장점이 여기서 나올 수 있다...)

지금보니 해쉬 비슷하게 생기긴 했다 ㅋㅋㅋ

pseudo code로 볼때 array[d(i)] = true, if(array[i] == false) -> 셀프 넘버라는 말인 거다!

#include <cstdio>
bool d[10001];
int df(int n)
{
    int res = n;
    while (n) {
        res += n % 10;
        n /= 10;
    }
    return res;
}
 
int main()
{
    for (int i = 1; i <= 10000; ++i) {
        d[df(i)] = true;
        if (!d[i]) printf("%d\n", i);
    }
    return 0;
}

ps. bool배열을 쓰는 게 메모리를 충분히 줄일 수 있다.