셀프 넘버들의 합 구하기

오밤중에 심심해서 이런 일을 했다. 퀴즈를 푸는 일.

1번 설명

어떤 자연수 n이 있을 때, d(n)을 n의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 
예를 들어 d(91) = 9 + 1 + 91 = 101 
이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1, 3, 5, 7, 9, 20, 31 은 셀프 넘버 들이다.

1번 문제

1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

 

출처: http://madchick.egloos.com/1385134

 

 

오호 문제는 간단해보이는군... 하고 도전했다가 새벽 3시가 되어버렸다. 2시간 가까이 지나버렸다. 고심하다가 GG치고, 답을 찾아봤다. 나오긴 했다: http://devrio.egloos.com/57173. 하핫... 대충 알긴 하겠는데 왜 이리 복잡한지. 이해하는 걸 포기하고 ^^ 다시 고심해서 짜보았다. 오옷 다른 사람이 짜놓은 걸 봐서 그런가, 이제는 금방 짰다. 그런데... 막상 하고 나서 다른 분이 작성한 걸 비교해보니, 접근한 방법은 비슷한 것 같다... ^^; 그래도 내쪽이 코드가 단순해서 유지 보수성이 좋고, 또한 힙을 쓰지 않아 메모리 액세스 측면에서 더 낫겠지 하고 위안해본다 -_-; 하지만 속도가 느린 나머지 연산이나 나누기 연산을 사용한 점은 OTL... 암튼 측정해보니 내 쪽이 20배 더 빠르다... ^o^ 역시 힙 액세스는 무섭다...

1326479118_testNexon.cpp

#include "stdafx.h"
#include <iostream>
#include <functional>
#include <bitset>

 

int _tmain(int argc, _TCHAR* argv[])
{
    const int endNumber = 4999;
    // LUJ, 가우스님이 10살 -_-때 발명하신 방법으로 1~4999까지의 합을 구한다
    int total = endNumber * (endNumber + 1) / 2;

    // 123 -> 6으로 변환하는 람다 재귀 함수
    const std::function< int(int) > SumDigit = [&SumDigit](int value) {
        return 0 == value ? 0 : (value % 10) + SumDigit(value / 10);
    };

 

    // 632 바이트

    std::bitset< endNumber > bitSet;

 

    for(int i = 1; i <= endNumber; ++i)
    {
        const int generator = i + SumDigit(i);

  

        if(endNumber > generator &&
           false == bitSet.at(generator))
        {
           // 제네레이터로 판명된 경우, 해당 값을 합에서 뺀다
           total -= generator;

   

           // 다시 빼지 않도록 표시한다
           bitSet.set(generator);
        }
   }

 

   std::cout << total << std::endl;

   system("pause");
   return 0;
}