[백준/C언어] 4673번 - 셀프 넘버

백준 웹사이트 "4673번 - 셀프 넘버" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

4673번: 셀프 넘버

---

소스 코드

#include <stdio.h>
#include <stdbool.h> // boolean 이용

// 1. n을 입력했을 때, d(n)을 구하는 함수를 작성한다.
int find_dn(int n){
    int dn = n;
    while(n>0){
        dn = dn + n%10;
        n = n/10;
    }
    return dn;
}

// 2. 1부터 10000까지 진행하며, d(n)들의 배열 arr_dn을 만든다.
int main(void){
    int arr_dn[10000];
    for(int i=0; i<10000; i++){
        arr_dn[i] = find_dn(i+1);
    }

// 3. 1부터 10000까지의 수들 중, arr_dn에 포함되지 않는 수들을 출력한다.
    for(int num=1; num<=10000; num++){
        bool self_num = true;
        for(int j=0; j<10000; j++){
            if(num==arr_dn[j]){
                self_num = false;
            }
        }
        if(self_num)
            printf("%d\n", num);
    }
}

---

문제 풀이

1. n을 입력했을 때, d(n)을 구하는 함수를 작성합니다.

  첫 번째 단계는 'n'이라는 입력에 대해 'd(n)'을 출력하는 함수 find_dn을 작성하는 것입니다. Line 6에서 dn을 n이라는 값으로 선언한 후, Line 7 ~ 10의 while문을 통해 각 자릿수를 더하면, 최종적으로 반환하는 dn은 처음 숫자(n)에 자릿수들을 모두 더한 값이 됩니다.

 

2. 1부터 10000까지 진행하며, d(n)들의 배열 arr_dn을 만듭니다.

  1부터 10000까지의 수들을 차례로 find_dn에 넣어 d(n)값들을 구하고, 그 d(n)값들로 새로운 배열_dn을 만들어 줍니다. (이때, 중복된 수들이 있을 수 있지만 중요하지 않습니다.)

 

3. 1부터 10000까지의 수들 중, arr_dn에 포함되지 않는 수들을 출력합니다.

  1 ~ 10000 까지의 수들 중 셀프 넘버의 개수를 알아봅니다. 어떠한 숫자가 셀프 넘버이기 위해서는 d(n)들의 배열 arr_dn에 존재하지 않아야 합니다. 따라서 저희는 10000까지의 숫자들을 arr_dn의 모든 값과 비교하여 겹치지 않는 셀프 넘버들을 찾아냅니다. 이렇게 모든 경우를 직접 확인하는 (단순 무식한) 알고리즘을 '브루트포스 알고리즘'이라고 합니다.

  Line 23을 참고하면, boolean형을 이용합니다. 원래 C언어에는 true/false를 의미하는 boolean은 존재하지 않고, 0이면 false, 0이 아닌 수이면 true를 의미합니다. 그러나 최근 C언어(ex. C99)에는 boolean이 존재하여 위와 같이 사용할 수가 있습니다. 사용하기 위해서는 Line 2와 같이 #include <stdbool.h>를 통해 헤더 파일을 추가해주어야 합니다.