[DP] 셀프 넘버 self number

셀프 넘버

---

* 넥슨 입사 문제 중 가장 쉬운 문제라고도 알려진 내용이라고 합니다.

 

 

 

 

 

1949년 인도 수학자 D.R. Kaprekar가 이름 붙인 셀프 넘버란?

---

양의 정수 n에 대해서 d(n)을 n과 n의 각 자리수를 더하는 함수라고 정의할 때, n을 d(n)의 생성자(Generator)라고 한다.

생성자가 없는 숫자를 셀프 넘버라고 한다.

 

n이 주어졌을 때, n, d(n), d(d(n)), d(d(d(n))), ...과 같은 무한 수열을 만들 수 있다.

 

 

 

 

 

 

 

 

 

예시

---

- d(75) = 75+7+5 = 87 이므로 87은 셀프 넘버가 아니다.

- 생성자가 한 개보다 많은 경우 : 101

d(91) = 91 + 9 + 1 = 101

d(100) = 100 + 1 = 101

 

 

 

 

 

 

 

 

 

 

저의 모자란 코드

---

 

문제 : 1~100까지의 숫자 중 셀프 넘버를 출력!

 

#include 
using namespace std; 
int main(){ 
     
    bool arr[100 + 1] = { false };//모두 셀프 넘버라고 초기화 
    int tmp =0; int i = 1; 
     
    for(;i<=100;i++){ 

        tmp = i; 
        int tmp_i = i; 
        while(tmp_i>0){ 
            tmp += (tmp_i%10); 
            tmp_i /= 10; 
        } 
        if (tmp<=100){ 
            arr[tmp] = true; //생성자가 있으므로 셀프 넘버가 아님 
        } 
    } 
     
    for(int i = 1;i<=100;i++){ 
        if (arr[i] == false) cout<<i<<endl; //셀프 넘버일 때 출력 
    } 
     
    return 0; 
} 

 

저는 0.1%정도 에라토스테네스의 체 느낌으로 풀었습니다.

i를 1부터 100까지 돌리되, d(i)만!을 계산하여 이 수는 셀프 넘버가 아니다, 라고 결정지었습니다.

 

처음에는 더 높은 비율로 에라토스테네스의 체 느낌으로 했는데, 왜냐하면 위에서 언급했던 무한수열이 하나뿐일 것이라고 성급히 판단했기 때문입니다.

 

n이 1일 때의 생성자 수열 : 2, 4. 6, 8, 10, 11...

이 때의 셀프 넘버 : 1, 3, 5, 7, 9...

 

이렇게 가야 하는데

 

n이 1에서부터 시작할 때의 수열 : 2, 4, 8, 16..

이 때의 셀프 넘버 : 1, 3, 6(...?????)

 

저는 왜인지 모르겠지만 이런식으로 생각해서 약간 삽질했습니다.

 

 

 

 

 

 

 

 

 

 

 

 

 

100보다 작은 셀프 넘버인 수 출력 (답 확인용)

---

총 13개 => 1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97

 

 

 

 

 

 

 

 

 

 

 

 

-

dp 시리즈는 저어어어ㅓ어어어어어어ㅓ어어어어어어ㅓ엉말 중요한 다이나믹 프로그래밍, 다시말해 동적 계획법으로 알고리즘을 짤 수 있도록 하는 꽤나 유명한 문제들을 소개해보려 합니다. 저의 부족한 실력으로나마 올려놓은 코드는 단순 참고용이며.. 이런 비효율적인 방법도 있네ㅎ 정도로만 봐주세요. 사실 푸는데 이게 동적 계획법인지도 잘 모르겠어서..ㅜㅜ. 이와 관련하여 조언 및 부족한 점은 언제든지 지적해주시면 감사드리겠습니다.