넥슨 입사문제 중에서

어떤 자연수 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 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

56개의 풀이가 있습니다. 1 / 6 Page

#include <stdio.h>
int getValueByGenerator(int);

int main(){
    int num[5000];
    int haveGenerator[5000] = {0,};
    int i =0;
    int result = 0;

    // n은 항상 d(n)보다 작으므로
    // i를 Generator로 가지는 값을 구하여 배열에 저장
    for(i=1; i<=5000; i++)
        num[i-1]= getValueByGenerator(i);

    for(i=0; i<5000; i++){
        // 1. num[i]값을 참조하여 Generator를 가졌는지 판단
        // 2. 5000이하인 경우 해당 인덱스 참조하여 Generator를 가졌는지 표시(1 = have, 0 = donthave)
        if(num[i] <= 5000)
            haveGenerator[(num[i] -1)] = 1;
    }

    // Generator를 가지지않은 값들을 모두 합하여 결과도출.
    for(i=0; i<5000; i++){
        if(haveGenerator[i] == 0){
            result += (i+1);
            printf("%d ", i+1);
        }
    }

    printf("\n\nresult : %d\n", result);
    return 0;
}

int getValueByGenerator(int x){
    return (x + x/1000 + (x%1000)/100 + (x%100)/10 + x%10);
}
합 : 1227365

*풀이방법 -> 주석

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <iostream>

using namespace std;
void calDNNumbers();
bool isNotSelfNumber(int number);

int dnNumbers[5000] = {0, };

int main() {

    int sum = 0;

    calDNNumbers();

    for(int i=1; i<=5000; i++) {
        if(!isNotSelfNumber(i)) {
            sum+=i;     
                }
    }

    cout << sum;
}

void calDNNumbers() {
    int f[4] = {0};

    for(int i=0; i<5000; i++) {
        f[0]=0, f[1]=0, f[2]=0, f[3]=0;
        f[0] = (i+1)/1000;
        f[1] = ((i+1)%1000)/100;
        f[2] = ((i+1)%100)/10;
        f[3] = (i+1)%10;

        dnNumbers[i] = f[0]+f[1]+f[2]+f[3]+(i+1);       
    }

}

bool isNotSelfNumber(int number) {
    bool isNotSelfNumber = false;
    for(int i=0; i<5000; i++) {
        if(dnNumbers[i]==number) {
            isNotSelfNumber = true;
            break;
        } 
    }
    return isNotSelfNumber;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <iostream>
#include <string>

using namespace std;

#define MAX 5000

bool list[MAX] = { false };
int Generator(int num) {
    int res = num;

    while (num != 0)
    {
        num /= 10;
        res += num % 10;
    }
    return res;
}


int main()
{
    for (int i = 1; i < MAX; i++) {
        list[Generator(i)] = true;
    }

    for (int i = 1; i < MAX; i++) {
        if (list[i] == 0) cout << i << endl;
    }

    return 0;
}


※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
int GetGenData(int nData)
{   
    int nGen = nData;
    do
    {
        nGen += nData%10;
    }
    while(nData/= 10);
    return nGen;        
}
int _tmain(int argc, _TCHAR* argv[])
{
    char chHasGen[5001];
    memset(chHasGen,0,5001);
    for(int iter = 1 ;iter <= 5000 ; iter ++)
    {
        int nGen = GetGenData(iter);
        if(nGen <= 5000)
        {
            chHasGen[nGen] = 1;
        }
    }
    int nResult = 0;
    for(int iter = 1 ;iter <= 5000 ; iter ++)
        if(chHasGen[iter] == 0)
            nResult += iter;
    printf("%d",nResult);
    return 0;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

C++11 입니다.

#include <iostream>
#include <set>
#include <numeric>

class SelfNumbersIn
{
public:
  SelfNumbersIn(const int& range) {
    for (int i = 1; i < range; ++i) numbers_.insert(i);
    for (int i = 1; i < range; ++i) numbers_.erase(d(i));
  }
  int Sum() const {
    return std::accumulate(numbers_.begin(), numbers_.end(), 0);
  }
private:
  int d(int n) {
    int sum = n;
    while(n > 0) {
    sum +=  n % 10;
    n = n / 10;
    }
    return sum;
  }
  std::set<int> numbers_;
};

int main()
{
  std::cout << SelfNumbersIn(5000).Sum() << std::endl;
  return 0;
}

$ g++ generator_c11.cpp -std=c++11 && ./a.out
1227365
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

c언어로 짜보았습니다.

#include <stdio.h>
#define MAX 5000
int Return_Generator(int number);
typedef enum {false, true} bool;


int main()
{
    // 1차원 배열로 인덱스+1 = N,  배열의 값이 false이면 셀프넘버.  배열의 값이 true이면 제네리이터라고 한다
    int CheckGen[MAX];
    int i;
    int Gen_index=0;
    int sum=0;

    // 배열 초기화
    for(i=1; i < MAX; i++)
    {
        CheckGen[i]=false;
    }


    for(i=1; i < MAX; i++)
    {
        Gen_index=Return_Generator(i);
        if(Gen_index < MAX)  // 5000을 넘는 값은 문제의 범위를 넘어가기 때문에 알 필요가 없다.
        {
            CheckGen[Gen_index-1]=true;
        }
    }

    for (i=0; i < MAX; i++)
    {
        if(CheckGen[i]==false)
        {
         //   printf("%d  ", i+1);
            sum = sum+ (i+1);
        }
    } 
    printf("Sum= %d\n",sum);


}

// d(n)값을 리턴한다.
int Return_Generator(int number)
{
    int Return_Value=0;
    int TargetNumber=0;
    int LastNumber=0;

    TargetNumber=number;

    while(TargetNumber > 0)
    {
        LastNumber = TargetNumber % 10;
        TargetNumber=TargetNumber /10;
        if(TargetNumber == 0)
        {
            return Return_Value += LastNumber + number;
                // 마지막에 최고 자릿수의 넘버와, 자기자신을 더하고 리턴시킨다.
        }else{
            Return_Value += LastNumber;
        }
    }
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

코딩배운지 이제 1년 반 다되가는 고등학생입니다. 이제 c와 c++, 자바를 조금 할 수 있는데.. 여기 와 보니 전 우물안의 개구리였군요 ㅠㅠ 더 열심히 배우도록 하겠습니다!

노란띠 되려고 풀이 같지도 않은 풀이를 작성하네요 양해바랍니다.

코드:

#include <iostream>
#include <vector>

using namespace std;

int getGenerator(int);

void main() {

    vector<int> selfNumbers;
    int normalSum = 0;
    int generatorSum = 0;

    for(int i = 1; i < 5001; i++) {
        normalSum += i;

        int generator = getGenerator(i);
        bool overlap = false;
        for(int j = 0; j < selfNumbers.size(); j++)
        {
            if(selfNumbers[j] == generator)
            {
                overlap = true;
                break;
            }
        }

        if(!overlap && generator <= 5000) {
            selfNumbers.push_back(generator);
            generatorSum += generator;
        }
    }

    cout<<normalSum-generatorSum<<endl;
}

int getGenerator(int n)
{
    int sum = n;

    while(true) {
        sum += n % 10;
        n /= 10;
        if(n == 0)
            break;
    }

    return sum;
}

출력값 :

1227365

이렇게 짜 두었습니다. 방학이라 오랜만에 코딩하니 어렵네요.. 노가다 방식으로 무식하고 무난(?)하게

(1부터 5000까지 자연수 합) - (1부터 5000까지 제너레이터 합) = (1부터 5000까지 셀프넘버 합)

이렇게 구했네요.

이제부터 코드를 효율적으로 짜는 방법을 익혀야죠!! 화이팅!

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
#include <iostream>
using namespace std;

#define MAX 5000

int tempArr[MAX];

int calcNum(int a)
{
    int sum = a;
    while (a != 0)
    {
        sum += a % 10;
        a /= 10;
    }
    return sum;
}

bool checkSelfNum(int num)
{
    for (int j = 0; j < MAX; j++)
    {
        if (tempArr[j] == num)
        {
            return false; //셀프넘버x
        }
    }
    return true;//셀프넘버  
}

void init()
{
    int tmp = 0;
    for (int i = 0; i < MAX; i++)
    {
        tmp = calcNum(i);
        tempArr[i] = tmp;
    }
}

int main()
{
    init();

    int res = 0;

    for (int i = 0; i < MAX; i++)
    {
        if (checkSelfNum(i))
        {
            //cout << "self Number -> " << i << endl;
            res += i;
        }
    }
    cout << res << endl;
    return 0;
}

c++ 로 했구요 ... 속도가 느리네요.. 50000만 되도..;;ㅠ

2014/08/20 01:37

※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

여기 오늘 가입했습니다... 그냥 for문으로 노가다ㅠㅠ.....

/*어떤 자연수 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 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.*/

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

using namespace std;

int gener (int num);

int _tmain(int argc, _TCHAR* argv[])
{
    int self_num[5001]={0}; //제네레이터가 될때마다 1씩증가
    int i;
    int sum=0;//셀프넘버의 합

    for(i=1;i<5000;i++)
    {

        self_num[gener(i)]+=1;
        //제너레이션이 발생하면 그 자리에 맞는 값이 1씩증가 합니다.
        //gener[4988]=0이면 셀프 넘버
    }

    for(i=1;i<5000;i++)
    {
        if(self_num[i]==0)
        {
            cout<<i<<"  "<<self_num[i]<<endl;
            sum+=i;
        }
    }
    cout<<"1~5000까지의 self_number의 합은 "<<sum<<" 입니다.\n";
    return 0;
}

int gener(int num)
{
    int i=1000;
    int val=num;
    int a=0;

    while(i>0)
    {
        a=num/i;//각 자릿수를 구합니다.
        val+=a;//제너레이션
        num-=a*i;//젤앞의 수부터 차례대로 지웁니다.
        if(val>5000)
        {
            val=0;
            break;
            //만약 제너레이션 값이 5000이상이 나왔으면 0을 출력합니다.
        }
        i=i/10;
    }

    return (val);
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.
//C로 짰습니다.

#include <stdio.h>
#include <stdlib.h>

int get_Dn(int input);
int filtering_and_Sum(char* _filter, int size);

int main()
{
    int MaxNum, i, result;
    char* filter; //true, false값을 체크하는 array
    printf("자연수를 입력하시오 : ");
    scanf("%d", &MaxNum);
    filter = (char*)malloc(sizeof(char)*MaxNum);
    for (i = 0; i < MaxNum; i++){
        *(filter + i) = 1;
    }

    result = filtering_and_Sum(filter, MaxNum);
    printf("-----------------------------\n\n");
    printf("The Summation of Self_Number is : %d\n", result);

    free(filter);
    return 0;
}

int get_Dn(int input)
{
    int output;
    int divisor=10;
    output = input;
    for (; 10*input/divisor; input /= divisor){
        output += input % divisor;
    }
    return output;
}


int filtering_and_Sum(char* _filter, int size)
{
    int i;
    int sum = 0;
    for (i = 1; i < size+1; i++){
        if (get_Dn(i) <= size)
            _filter[get_Dn(i)-1] = 0; // Self_Num이 아닌 경우 false값 지정
    }
    printf("self_number from 1 to %d...\n", size);
    for (i = 1; i < size+1; i++){
        if (_filter[i-1]){
            printf("%d\n", i);
            sum += i;
        }
    }
    return sum;
}
※ 상대에게 상처를 주기보다 서로에게 도움이 될 수 있는 댓글을 달아 주세요.

풀이 작성

※ 풀이작성 안내
  • 본문에 코드를 삽입할 경우 에디터 우측 상단의 "코드삽입" 버튼을 이용 해 주세요.
  • 마크다운 문법으로 본문을 작성 해 주세요.
  • 풀이를 읽는 사람들을 위하여 풀이에 대한 설명도 부탁드려요. (아이디어나 사용한 알고리즘 또는 참고한 자료등)
  • 작성한 풀이는 다른 사람(빨간띠 이상)에 의해서 내용이 개선될 수 있습니다.
목록으로
코딩도장

코딩도장은 프로그래밍 문제풀이를 통해서 코딩 실력을 수련(Practice)하는 곳입니다.


언어별 풀이 현황
전 체 x 364
python x 119
기 타 x 58
java x 67
matlab x 5
scala x 8
cs x 15
cpp x 56
php x 6
delphi x 3
ruby x 6
haskell x 2
lisp x 2
javascript x 5
r x 2
clojure x 2
erlang x 1
perl x 1
objectivec x 5
go x 1