[백.단.풀.5] 셀프 넘버 (4673)

Step : <함수 사용하기>

Title : " 셀프 넘버 "

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	6946	3796	3165	56.589%

문제

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다. 양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의하자. 예를 들어, d(75) = 75+7+5 = 87이다.

양의 정수 n이 주어졌을 때, 이 수를 시작해서 n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다. 

예를 들어, 33으로 시작한다면 다음 수는 33 + 3 + 3 = 39이고, 그 다음 수는 39 + 3 + 9 = 51, 다음 수는 51 + 5 + 1 = 57이다. 이런식으로 다음과 같은 수열을 만들 수 있다.

33, 39, 51, 57, 69, 84, 96, 111, 114, 120, 123, 129, 141, ...

n을 d(n)의 생성자라고 한다. 위의 수열에서 33은 39의 생성자이고, 39는 51의 생성자, 51은 57의 생성자이다. 생성자가 한 개보다 많은 경우도 있다. 예를 들어, 101은 생성자가 2개(91과 100) 있다. 

생성자가 없는 숫자를 셀프 넘버라고 한다. 100보다 작은 셀프 넘버는 총 13개가 있다. 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

10000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

입력

입력은 없다

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

예제 입력 

예제 출력 

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

이번 문제는 조금 난이도가 있었다.

우선 이번 문제에서 특이한 점은 input 이 없다는 것이다.

즉, output이 일정하게 정해져 있다는 것이고, 이런 문제는 모든 정답을 미리 배열에 넣어놓고

꺼내면서 출력하는 문제이다. (비슷한 문제로 저번에 포스팅한 "설탕 배달"이 있었다.)

이번 문제에서 시간이 걸렸던 곳은

drKaprekar 함수를 만드는 과정에서 시간을 소요했다.

함수에서 1~9, 10~99, 100~999, 1000~9999, 10000 의 범위에서 각 숫자를 자리수 마다 끊어서

계산을 해야되서 이 것을 하나씩 노가다로 하지 않고 이중 for문으로 어떻게 해야 간결하게 코딩을 할 수 있을까라는

고민을 하면서 시간을 소요했다.

결국 2중 for문으로 해결했고, 각 자리 수를 가져오는 방법은 (자리의 길이-1)만큼 10으로 나누고 마지막에 나머지 연산 10 을 하면 된다.

그리고 그 함수를 1부터 최대 범위인 10000까지 함수를 수행하면서 나왔던 숫자들을 visit 처리하고,

마지막에 visit 처리가 되지 않은 숫자를 출력하면 답이 된다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <malloc.h>
 
int arr[10001];
 
int drKaprekar(int n, int divCnt)
{
    int storage, sum = n;
 
    for (int i = 1; i <= divCnt; i *= 10)
    {
        storage = n;
        for (int j = 1; j < i; j*= 10)
            storage /=  10;
        sum += (storage % 10);
    }
 
    return sum;
}
 
int main()
{
    for (int i = 1; i <= 10000; i++)
    {
        if (arr[i] == 0)
        {
            int flg = 1, tmp = i;
            while (flg <= 10000)
            {
                if (tmp < 10) flg = drKaprekar(tmp, 1);
                else if (10 <= tmp && tmp < 100) flg = drKaprekar(tmp, 10);
                else if (100 <= tmp && tmp < 1000) flg = drKaprekar(tmp, 100);
                else if (1000 <= tmp && tmp < 10000) flg = drKaprekar(tmp, 1000);
                else flg = drKaprekar(tmp, 10000);
 
                tmp = flg;
                if (flg == i) break;
                else if (flg <= 10000) arr[flg] = 1;
                else break;
            }
        }
    }
 
    for (int i = 1; i <= 10000; i++)
        if (arr[i] == 0)
            printf("%d\n", i);
 
    return 0;
}