[Baekjoon/백준][4673][C/C++] 셀프 넘버

『목차』
0. 개요
1. 문제
2. 풀이
3. 코드

0. 개요

해당 문제의 알고리즘 분류 중 하나는 '브루트포스 알고리즘'으로, 모든 경우의 수를 일일이 따져보며 풀어야 하는 문제이다. 문제에 제시된 self number에 대한 개념만 이해한다면 쉽게 풀 수 있는 문제이다.

1. 문제

https://www.acmicpc.net/problem/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]

없음.

[예제 출력 1]

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

2. 풀이

우선, Self Number에 대하여 이해해 보자. 

$d(1)$	$=1+1$	$=2$	1은 2의 생성자 [2 : 셀프넘버X]
$d(2)$	$=2+2$	$=4$	2는 4의 생성자 [4 : 셀프넘버X]
$d(3)$	$=3+3$	$=6$	3은 6의 생성자 [6 : 셀프넘버X]
...
$d(41)$	$=41+4+1$	$=46$	41은 46의 생성자 [46 : 셀프넘버X]
...
$d(9999)$	$=9999+9+9+9+9$	$=10035$	9999는 10035의 생성자 [10035 : 셀프넘버X]
$d(10000)$	$=10000+1+0+0+0+0$	$=10001$	10000은 10001의 생성자 [10001 : 셀프넘버X]

Self Number의 원리는 위와 같다.

 

d(1)부터 d(10000)까지의 값을 구하면 10000 이하의 Self Number가 아닌 모든 수가 구해진다. (∵d(10000)부터는 그 값이 무조건 10000을 넘어가기 때문.) 따라서, 길이가 10000인 배열을 만든 후 (index가 1번부터 시작한다 가정했을 때 길이가 10000이다. c에서는 길이가 10001인 배열을 만들어야 1번부터 10000번까지의 수를 다룰 수 있다.) Self Number에 해당하지 않는 번호를 지워가다 보면, 마지막엔 Self Number에 해당하는 번호만이 남게 된다. 

 

배열은 단순 체크 용도이므로, 자료형이 bool인 배열을 선언하여 trueㆍfalse 여부만 판단하게 만들었다. 자세한 구현 내용은 주석을 참고 바란다.

3. 코드

#pragma warning (disable:4996)
#include <stdio.h>
#include <stdbool.h>//bool 자료형 사용 목적

bool flag[10001]; 
/* 
main 함수 내부에 배열 선언 시, 스택영역 메모리 초과로 실행 안됨.
따라서, 전역변수로 선언하여 데이터영역에 할당해야함.
*/

int d(int n) {
	return n + (n % 10) + ((n / 10) % 10) + ((n / 100) % 10) + ((n / 1000) % 10);
}
/*
더욱 범용적(일반적)인 방법으로 d함수를 정의할 수도 있지만,
여기서는 10000 이하의 수로 범위가 제한되어 있으므로, 
해당 상황에서만 함수가 작동하도록 코드를 설계하였다.
*/

int main(int argc, char* argv[]) {

	for (int i = 1; i <= 10000; i++)
		flag[d(i)] = true;	//self number에 해당하지 않는 값을 true로 변경.

	for (int i = 1; i <= 10000; i++)
		if (flag[i] == false)	//self number에 해당하는 값은 false이다.
			printf("%d\n", i);

	return 0;
}