4673번: 셀프넘버

2018.12.23.

문제 출처:  

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

문제 분석: 

문제를 살펴보면 n과 n의 각 자리수를 더하는 함수가 있다고 했을때 이를 실행해서 값이 나오게하는 것을 생성자라고 한다.

ex) 33-> 33+3+3=39

33은 39의 생성자

이와 같을때 생성자가 없는 숫자를 셀프넘버라 한다.

1~10000까지의 셀프넘버를 출력하라

문제 해결:

arr[10000]에 1~10000까지 값을 각각 넣어주고

arr[0]=1 arr[1]=2 .....

FindSelf()라는 함수를 실행한다

이 함수는 숫자를 넣었을때 생성자를 되게 하는 값을 만든다

ex) FindSelf(33) = 39

그리고 생성자가 있는 배열에는 0을 넣어준다.

arr[10000]을 확인해주면 셀프넘버에는 자기자신이 들어가 있고 셀프넘버가 아닌값에는 0이 들어가있다.

내 소스코드:

#define _CRT_SECURE_NO_WARNINGS   
#include <stdio.h>    
 
int FindSelf(int i);
 
int main()
{
    int arr[10000];
    int num;
 
 
    for (int i = 1;i < 10001;i++)
    {
        arr[i-1] = i;
    }
 
    for (int i = 1;i < 10001;i++)
    {
        num = FindSelf(i);
        if (num < 10000)
        {
            arr[num-1] = 0;
        }
    }
 
    for (int i = 0;i < 9999;i++)
    {
        if (arr[i] != 0)
        {
            printf("%d\n", arr[i]);
        }
    }
}
 
int FindSelf(int i)
{
    int total = 0;
    total += i;
 
    while (i != 0)
    {
        total += i % 10;
        i /= 10;
    }
    return total;
}
 

실행결과:

고찰:

지금 쓴 방법이 "에라토스테네스의 체"라고 소수를 구할때 많이 쓰는 방법이다.