셀프 넘버 [함수 / 4673번 / 6단계(1) / C#]

4673번: 셀프 넘버

문제

셀프 넘버는 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

코드

using System;
using System.IO;
using System.Text;


class Program {

    //함수 d(n)을 정의해보고 공식을 만들어보자.
    //역으로 생성자를 확인하는 함수를 만들수 있는지 확인해보자.

    //만약 생성자를 역추적하여 확인할수 있다면
    //생성자 확인이 불가능할때까지 역으로 돌린 뒤 숫자를 출력한다.
    //while문으로 돌려보자.

    //문제 설명에 나온 함수 d(n)
    static int Creater(string num)
    {
        int result = int.Parse(num);
        for (int i = 0; i < num.Length; i++)
        {
            result += int.Parse(num[i].ToString());
        }

        return result;
    }

    static void Main()
    {
        //생각해보니 역으로 생성자가 누구인지 확인하기 어렵다.
        //그냥 10000줄의 수를 stringBuilder에 집어넣고
        //함수 d(n)에서 나온 수를 다 제거하여 남은 수만 출력하면
        //10000보다 작거나 같은 셀프넘버만 남게된다.

        //생성자로 인해 생성된 값을 받습니다.
        int[] created_Values = new int[10000];
        for (int i = 0; i < 10000; i++)
        {
            created_Values[i] = Creater(i.ToString());
        }

        //셀프넘버값을 받을 스트링빌더를 생성합니다.
        StringBuilder selfNumber = new StringBuilder();

        //반복문을 돌면서 각 값을 created_Values[](생성된값)와 비교하며 문자열을 채웁니다.
        bool isSelfNumber = true;
        for (int i = 0; i < 10001; i++)
        {
            for (int j = 0; j < created_Values.Length; j++)
            {
                if(i == created_Values[j])
                {
                    isSelfNumber = false;
                    break;
                }
                else
                {
                    isSelfNumber = true;
                }
            }

            if (isSelfNumber) selfNumber.AppendLine(i.ToString());
        }

        //마지막까지 채워진 SelfNumber문자열을 출력합니다
        Console.WriteLine(selfNumber);
    }
}

문제를 푼 순서는 위 주석대로입니다. 처음엔 d(n)함수를 구현하고, 이 함수를 통해 나온 값의 규칙을 가지고 생성자를 찾아내는 공식을 만들어서, 생성자가 찾아지지 않을때까지 생성자를 찾고나서 최종적으로 셀프넘버를 구하려고 했습니다.

 

하지만 그게 좀 어려웠습니다. 때문에 d(n)을 1~10000번까지 수행하면서 모든 값을 구했습니다. 그리고 스트링 빌더에 1~10000까지의 수를 넣는 반복문을 만들고 각 수가 들어갈때 d(n)을 토해 구한 모든 값과 비교해보면서 해당하는 수는 스트링빌더에 넣지 않는 방식으로 문제를 풀었습니다.

 

이상입니다.

 

콘솔실행

정상적으로 출력됩니다!