[백준 4673] 셀프 넘버

• 안녕하세요. BlockDMask 입니다.

• 추석날 2번째 문제 입니다. 왔다 갔다 차안에서 문제를 풀고 있습니다. 길이 많이 막히네요;;

170818 문제 빼먹음 -> 171004 완료

0. 제목

• 백준 4673 셀프 넘버

• BOJ 4673 self number

1. 문제 설명

셀프 넘버는 1949년 인도 수학자 D.R. Kaprekar가 이름 붙였다.

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

예를 들어 d(42) = 42 + 4+ 2 = 48 이다.

양의 정수 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일은 생성자가 91, 100으로 두가지 이다.

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

100보다 작은 셀프 넘버는 총 13개가 있다.

1, 3, 5, 7, 9, 20, 31, 42, 53, 64, 75, 86, 97.

10,000 보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

2. 풀이 설명

a) 10001 의 index를 가진 bool type 배열을 선언 및 초기화 합니다.

b) 배열의 index (1~10000) 숫자를 하나씩 solution 함수에 넣어서 확인합니다.

숫자가 들어오면

자기 자신의 숫자 n 과

자기 자신의 숫자의 1의 자리

자기 자신의 숫자의 10의 자리

자기 자신의 숫자의 100의 자리

.

.

.

를 계속 더해줘서 생성자를 가진 수를 판별합니다.

c) 생성자를 가진 숫자를 판별해서 빼줍니다. (true로 변경)

d) 배열의 남아있는 숫자를 출력합니다. (false인 수 출력)

3. 코드

//BOJ 4673 셀프넘버
 
#include<iostream>
#include<cstdio>
#define N 10001 //배열 arr[1 ~ 10000] 까지 이므로 10001.
 
using namespace std;
bool arr[N];
 
//셀프넘버 판별 함수.
int solution(int n){
    int sum = n;    //자기 자신을 먼저 더해주고
 
    while(1){   // 각 자리수의 숫자를 더해야하므로 1의 자리를 계속 더해준다.
 
        if(n == 0) break; //0이 되면 break
        sum += n%10;      //1의 자리 더해주기
        n = n/10;         //한자리씩 없애기
 
    }
 
    return sum;
}
 
 
int main(void){
 
    for(int i=1; i<N; i++){
        int idx = solution(i);
 
        if(idx <= N){
            arr[idx] = true;    //셀프넘버 아닌 수 true 로 변경
        }
 
    }
 
    //출력
    for(int i=1; i<N; i++){
        if(!arr[i]) printf("%d\n", i);
    }
 
    return 0;
}

4. 인증

문제 출처 - https://www.acmicpc.net/problem/4673

감사합니다. 하트 꾹 부탁드립니다.!!