4673) 6. 함수 : 셀프 넘버(Self Number)

문제

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

4673번: 셀프 넘버

 

내 코드

33 -> 33 + 3 + 3 = 39라서 생성자라면 1 -> 1 + 1 = 2 니까 1도 생성자 아닌가?라고 생각했다. 예제에 나오는 100 이하의 self number가 어떻게 구해지는지 이해하기 위해 한참을 구글링하다 반대로 생각해야 함을 깨달았다.

 

즉, 만드는 숫자(ex. 1, 33)에 초점을 두는 게 아니라 만들어진 숫자(ex. 2, 39)에 초점을 두어야 구분이 된다. 예를 들어 2는 앞에 있던 1이 1 + 1 = 2로 만들어지므로 self number가 아니고, 4 역시 2 + 2 = 4 조합으로 만들어지므로 마찬가지로 self number가 아니다.

반면 3은 이전 수들로 조합이 만들어지지 않으므로 self number이고, 5 역시 마찬가지이다.

그렇기 때문에 10은 5 + 5 로 self number가 아니지만 20은 14 -> 14 + 1 + 4 = 19, 15 -> 15 + 1 + 5 = 21로 조합이 만들어지지 않아 self number에 해당되어 10은 안되고 20은 되는(?) 수열이 된다.

 

자세한 설명은 위키피디아 참고!

 

처음엔 그냥 함수 d로 구하는 수들을 vector 써서 배열에 넣고 쭉 출력하면 되겠네.. 했었는데 이해하고보니 그 짓을 했다간 오히려 생성자를 구하는 데다가, 생성자 구한걸 10000 크기의 배열에서 제외한 값들만 뽑아내는 건 더 무식한 짓이어서 3052 문제의 방법을 적용했다.

#include "stdio.h"

#define MAX 10001				// 작거나 같아야함

int d(int num) {
    int temp(num);

    while (num != 0) {
        temp += num % 10;			// ex) 1 -> 1 + 1 = 2
        num /= 10;
    }
    return temp;				// 2는 생성자
}

int main() {
    int gen(0); 
    bool a[MAX]{ false };

    for (int i(0); i < MAX; i++) {
        gen = d(i);
        if (gen < MAX) a[gen] = true;
        // 생성자가 지정한도를 초과하지 않는 경우에 한해 체크
        if (!a[i]) printf("%d\n", i);		// self number들만 출력
    }

    return 0;
}