[BOJ][C] 4673번 셀프 넘버

안녕하세요.

오늘은 백준 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보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 출력하는 프로그램을 작성하시오.

 

입력

입력은 없다.

 

출력

10,000보다 작거나 같은 셀프 넘버를 한 줄에 하나씩 증가하는 순서로 출력한다.

 

예제 입력

 

예제 출력

1
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

 

제한

시간 제한: 1초

메모리 제한: 256MB

 

---

풀이

문제에서 요구하는 셀프 넘버는 생성자가 한 개도 없는 숫자이므로, 1부터 10,000까지의 숫자 중 생성자가 한 개 이상인 숫자들은 출력하지 않으면 됩니다.

 

따라서 1부터 10,000까지의 숫자를 차례대로 d(n)이라는 숫자에 넣어서 나온 숫자는 생성자가 한 개 이상인 경우므로 출력하지 않도록 체크합니다.

이때 9979와 같은 숫자들은 d(n)의 값이 10,000을 넘어가므로 무시해줍니다.

 

이제 d(n) 함수를 만들어서 n과 각 자릿수를 더하게 만들어 보겠습니다.

 

각 자리수를 더하는 것은 더하기 사이클 문제(링크)에서도 볼 수 있듯이 일의 자리부터 구하고 자릿수를 줄여나가는 방식으로 만들 수 있습니다.

 

코드로 작성하면 d(n) 함수는 다음과 같습니다.

 

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

 

 

그 후 배열을 생성해 1부터 10,000까지의 숫자를 넣은 후, d(n)에 해당하는 배열 원소는 0으로 넣어 체크를 해줍니다.

 

마지막으로 배열 전체를 검사해 원소가 0 아니면 출력하도록 작성해주면 됩니다.

 

정답

#include <stdio.h>

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

int main()
{
	int arr[10000];
	for (int i = 0; i < 10000; i++)
	{
	    arr[i] = i + 1;
	}
	for (int i = 1; i <= 10000; i++)
	{
	    int res = d(i)-1;
	    if(res <= 10000)
	        arr[d(i)-1] = 0;
	}
	for (int i = 0; i < 10000; i++)
	{
	    if (arr[i] != 0)
	        printf("%d\n", arr[i]);
	}
	return 0;
}

 

---

오늘은 백준 4673번 셀프 넘버 문제를 풀어보았습니다.

 

댓글로 질문을 남기시면 성실히 답해드리겠습니다

 

감사합니다!