카프리카 상수 구하기

이번에 풀어볼 알고리즘은 카프리카 상수 구하기이다. 

어떤 자연수 n이 있을때, d(n)을 n의 각 자릿수 숫자들과 자기 자신을 더한 숫자라고 정의하자. 예를 들어 d(91) = 9 + 1 + 91 = 101 이다. 이 때, n을 d(n)의 제너레이터(generator)라고 한다. 위의 예에서 91은 101의 제너레이터 이다.

어떤 숫자는 하나 이상의 제너레이터를 가지고 있는데 101의 제너레에티는 91뿐 아니라 100도 있다. 그런데 반대로 제너레이터가 없는 숫자들도 있고, 이런 숫자는 수학자 카프리카가 셀프넘버라 이름을 붙였다.

예로 1, 3, 5, 7, 9, 20, 31은 셀프 넘버들이다.

입력) 첫 번째 줄에 테스트 케이스의 수 T가 주어진다.(1 <= T <= 50)

시작(a) 값과 마지막 값(b)가 입력되면 두 수 사이의 셀프넘버의 합을 구하라. (1 <= a <= b <= 5,000), 

입력)

4  // TC 갯수

1 10  // 시작 값(a), 마지막 값(b)

1 1

2 10

10 59

출력)

Case #1

25

Case #2

1

Case #3

24

Case #4

146

Solution)

비교적 간단하게 풀릴 수 있는 문제이다. 처음 값과, 마지막 값에 해당하는 a, b가 1이상 5000 이하이기 때문에 1부터 5000까지 각각 계산을 해서 나오는 값 제거해 나간다. 그리고 남은 수를 주어진 a, b 사이에 몇개가 있는지 합을 구해 출력하면 될 것 같다. 복잡도도 n에 해당해서 50개의 TC도 1초 내에 무난히 수행될 수 있다. 이제 coding을 해보자. 한가지 주의할 점은 마지막 수의 MAX는 5000까지지만 실제로 계산하면 5005가 나오듯이 계산한 값을 data 라는 배열에 check 해주기 위해 MAXN을 5050까지 잡았다.(4999를 계산하면 5030 이 나옴)

#include <stdio.h>

#define MAXN 5050

int main(void)

{

int T;

int a, b;

int data[MAXN + 1] = { 0, };

scanf("%d", &T);

//check the self-number

int selfNum;

for (int i = 1; i <= 5000; ++i){

if (i < 10){

selfNum = i + i;

}

else if(i >= 10 && i < 100){

selfNum = i / 10 + i % 10 + i;

}

else if (i >= 100 && i < 1000){

int first = i / 100;

int second = (i - first * 100) / 10;

int third = i - first * 100 - second * 10;

selfNum = first + second + third + i;

}

else{

int first = i / 1000;

int second = (i - first * 1000) / 100;

int third = (i - first * 1000 - second * 100) / 10;

int forth = i - first * 1000 - second * 100 - third * 10;

selfNum = first + second + third + forth + i;

}

data[selfNum] = 1;

}

for (int test_case = 1; test_case <= T; ++test_case){

scanf("%d %d", &a, &b);

int sum = 0;

for (int i = a; i <= b; ++i){

if (data[i] == 0) sum += i;

}

printf("Case #%d\n%d\n", test_case, sum);

sum = 0;

}

return 0;

}