Heart 님의 블로그에서 트랙백, 넥슨 입사시험 문제로 더 유명한 '셀프 넘버' 문제
어떤 자연수 n이 있을 때, d(n) 을 n 의 각 자릿수 숫자들과 n 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101 이라 하고 이 때, n을 d(n)의 제네레이터(generator)라고 한다. 위의 예에서 91은 101의 제네레이터이다. 어떤 숫자들은 하나 이상의 제네레이터를 가지고 있는데, 101의 제네레이터는 91 뿐 아니라 100도 있다. 그런데 반대로, 제네레이터가 없는 숫자들도 있으며, 이런 숫자를 인도의 수학자 Kaprekar가 셀프 넘버(self-number)라 이름 붙였다. 예를 들어 1,3,5,7,9,20,31 은 셀프 넘버 들이다.
문제.
1 이상이고 5000 보다 작은 모든 셀프 넘버들의 합을 구하라.
이 문제에는 속임수가 있는데, 그것은 합을 구하라는 것이다. 즉, 셀프 넘버를 직접 구하란 소리는 아니다. 따라서 1과 5000의 합에서 셀프 넘버가 아닌 숫자 즉, 제너레이터를 가진 숫자를 빼면 된다.
라고 쉽게 생각했더니, 결과가 안나오거나 코드가 지저분해지는 일이 발생. 그래도 결국 만족할 만한 코드는 나왔다. 제너레이터에 의해 출력된 넘버가 겹칠 수 있으므로 이를 걸러야 한다. 라는 것이 가장 큰 난제였는데, 잘 생각해 보면, 제너레이터에 의해 발생하는 숫자들은 순차적으로 나열했을 때 홀수끼리와 짝수끼리만큼은 순서가 섞이는 일이 없다. 따라서 홀수, 짝수 별로 최대값 검사를 하면 별도의 오버헤드 없이 쉽게 거를 수 있다.
#include <stdio.h>
#include <stdlib.h>
long d(long number) {
long result = number;
while(number > 0) {
result += number % 10;
number /= 10;
}
return result;
}
int main(void) {
long i, number, result, buffer;
long odd = 0, even = 0, parity;
printf("Input number : ");
scanf("%d", &number);
result = (number + 1) * number / 2;
for(i = 1; i < number; i++) {
buffer = d(i); parity = buffer & 1;
if(number < buffer) break;
if(1 == parity && buffer > odd) {
odd = buffer;
result -= buffer;
}
else if(0 == parity && buffer > even) {
even = buffer;
result -= buffer;
}
}
printf("%d\n", result);
system("pause");
return 0;
}
