39. C++ 백준 4673 번 셀프 넘버

안녕하세요! 코딩하는 덕구입니다.

함수 d를 정의하여 푸는 문제인 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

https://www.acmicpc.net/problem/4673

4673번: 셀프 넘버

 

#include <iostream>
using namespace std;
int arr[10000] = {0,};

void d(){
    int a,b,c,d,sum; //1,2,3,4 번째 자리의 수, sum 은 합
    for(int i = 1; i<10000; i++){
    	// i 는 숫자
        a = 0; b = 0; c = 0; d = 0; //반복시마다 값 초기화
        d = i%10; //숫자의 4번째 자리
        c = (i%100)/10; //숫자의 3번째 자리
        b = (i%1000)/100; //숫자의 2번째 자리
        a = (i%10000)/1000; //숫자의 1번째 자리
        sum = i + a + b + c + d; //sum 은 숫자 + 각 자리수의 합
        arr[sum] = 1; //sum 값이 나오면 1로 표시
    }
}

int main(){
    d(); //함수 d 실행
    for(int i=1; i<10000; i++)
        if(arr[i] == 0)
            cout<<i<<endl; //arr 안의 번호가 0 인 것을 출력 (sum으로 안나왓던 값을 출력)
    return 0;
}

 

예를들어 숫자 8976 이 있으면 8을 1번째, 9를 2번째, 7을 3번째, 6을 4번째 자리로 생각하고

숫자는 1~10000 까지만 들어오고 어차피 self 넘버는 10000이 아니기 때문에 (문제 출력에 나와있음)

9999까지만 검색하면 되기 때문에 숫자의 4 자리까지만 알고리즘을 만들었습니다!

 

숫자의 1, 2, 3, 4 번째 자리를 변수 a, b, c, d 에 아래와 같이 계산해서 대입하도록 함수를 작성했고,

4번째 자리는 숫자 % 10

10으로 나눠서 나머지만 구하면 마지막 자리수가 나오겠죠!

3번째 자리는 (숫자 % 100)/10  

100으로 나눠서 나온 나머지에서 10으로 나누면 10의 자리만 남고, 1의 자리는 버리겠죠!

추가로 10단위가 아니라 1 이 되겠죠 !

예를들어 168 % 100 = 68,  68 /10 = 6 이런식으로 저희가 의도한 숫자를 구했습니다!

2번째, 1번째 자리의 원리도 같아요!

 

그렇게 나온 값 들을 현재 숫자 i 와 각 자리수 a, b, c, d 를 더해줘서 sum 에 대입하고

sum 이 지금껏 한번이라도 나왔는지 표시할 (self 넘버가 아닌 숫자를 표시 할)목적으로 arr[sum] 에 1을 대입했습니다!

그렇게 9999 번까지 검사 하는 함수 d를 만들고

메인 함수 처음에 함수 d를 실행시킨 이후에 

for 문을 이용해서 배열 arr 안의 숫자가 0이면(한번도 나오지 않은 숫자 즉, self 넘버) 출력하는 

프로그램을 만들었습니다!  

 

C++ 백준 4673번 이었습니다!

감사합니다!