[C++] 백준 4673

백준 4673번 문제 셀프넘버이다.

 

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

 

 

이 문제는 코드작성도 작성인데 문제를 이해하는데 다른 문제보다 시간이 걸렸다.

길이부터가 장난이 아니다

 

그리고 예시를 보자

입력은 없고 출력만 있다.

 

간단히 말하면 위의 식에 맞는 생성자중 생성자가 아닌것을 찾으면 된다.

 

예를 들어, 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, ...

문제에서 예시를 든것처럼 하나 예시를 들자면 82로 시작을 한다 가정하자.

그러면 다음 숫자는 82 + 8 + 2 = 92로 92가 되고 그 다음 숫자는 92 + 9 + 2 = 103이 된다.

그리고 이렇게 생성된 숫자는 다음 숫자의 생성자가 되기 때문에 해당 식에 맞는 숫자들을 제거해주면 셀프넘버를 구할 수 있다.

 

다음은 코드이다.

#include <iostream>
using namespace std;

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

int main() {
	int a[10001] = { 0, };
	int num;
    
	for (int i = 1; i <= 10000; i++) {
		num = d(i);
		if (num <= 10000) {
			a[num] = num;
		}
	}
	for (int i = 1; i <= 10000; i++) {
		if (a[i] == 0)
			cout << i << endl;
	}

}

먼저 함수 d를 보면 while문을 이용한 간단한 계산식이다.

23 = 23 + 2 + 3 이런식으로 계산해야하기 때문에 n을 10으로 나눠가면서 sum과 합하였고 마지막에는 0이 되어 반복문이 종료되야하기 때문에 조건으로 n != 0을 하였다.

 

함수를 통해 계산한 값(num)은 배열의 각 수치에 입력된다.

예를들어 num=23인 경우 a[23] = 23 이런식으로 각각의 자리에 입력된다.

이걸 10000까지 반복하면 입력되지 않은 값들이 있는데 이 배열 번호를 출력하면 된다.