[백준] 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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdio.h>

int main() {
int i, num[10100] = { 0, };

for (i=1; i<=10000; i++) {
if (i < 10)
num[i + i]++;
else if (i >= 10 && i < 100)
num[i + (i/10) + (i%10)]++;
else if (i >= 100 && i < 1000)
num[i + (i/100) + ((i/10) - 10*(i/100)) + (i%10)]++;
else if (i >= 1000 && i < 10000)
num[i + (i/1000) + ((i/100) - 10*(i/1000)) + ((i%100)/10) + (i%10)]++;
}

for (i=1; i<=10000; i++) {
if (num[i] == 0)
printf("%d\n", i);
}

return 0;
}



출력 결과




메모

이 문제를 푸는 과정에서는 정수형 배열 num을 사용했다. 가장 먼저 배열에 들어가는 값들을 모두 0으로 초기화 시키고, 추가적으로 for문을 돌릴 때 필요한 임시 정수형 변수 i를 선언하였다. 1부터 10,000까지의 숫자를 확인하는 문제이기 때문에 해당 영역 안에서 조건을 나누어 보았는데, 그 값에 대한 조건 기준을 1-9, 10-99, 100-999, 1,000-9,999로 하여 각각 처리 방식을 달리 했다. 그 이유는 10자리, 100자리, 1,000자리가 있을 때, 각각의 자리 수를 확인하려면 그 숫자를 특정 값으로 나누어 몫을 찾거나 나머지 값을 찾아야 하는데, 10자리의 경우 10으로 나누면 몫과 나머지가 바로 나오지만 100자리의 경우, 예로 123이라는 숫자가 있을 때 100으로 나누는 경우 몫은 1이지만 나머지가 23으로 나오고, 10으로 나누는 경우엔 몫이 12이고 나머지가 3이기 때문에 더 복잡한 식이 필요했다. 10,000의 경우, 자리수를 더하면 10,001이 되어 범위에서 벗어나기 때문에 조건에서 제외시켰다. 이러한 계산 방식을 적용한 후에 결과 값에 해당하는 i번째 배열의 값을 하나씩 증가시키도록 하였다.

10자리에서 사용한 방식은 단순히 일의 자리를 두 번 더했다. 예를 들면, i가 8일 때, 8 + 8 = 16으로 계산하여 num[16] 에 들어가는 값을 하나 증가시킨 것이다. 100자리에서 사용한 방식은 원래의 값 + 원래의 값을 100으로 나눈 값 + (원래의 값을 10으로 나눈 값 - 10 * 원래의 값을 100으로 나눈 값) + 원래의 값을 10으로 나눈 나머지로 계산하였다. 단순히 말로만 설명하면 어렵기 때문에 이 또한 예를 들어보자면, 582라는 숫자가 있을 때, ① 원래의 값 : 582, ② 원래의 값을 100으로 나눈 값 : 5, ③ (원래의 값을 10으로 나눈 값 - 10 * 원래의 값을 100으로 나눈 값) : 58 - 10 * 5 = 8, ④ 원래의 값을 10으로 나눈 나머지 : 2라고 계산 할 수 있다. 계산 결과, 582 + 5 + 8 + 2 = 597이라는 값이 나오고, num[597] 에 들어가는 값을 똑같이 하나 증가시켜준다.

마지막으로, 1,000자리에서 사용한 방식은 100자리보다 약간 더 복잡했다. 1,000자리에서는 원래의 값 + 원래의 값을 1,000으로 나눈 값 + (원래의 값을 100으로 나눈 값 - 10 * 원래의 값을 1,000으로 나눈 값) + (원래의 값을 100으로 나눈 나머지를 다시 10으로 나눈 값) + 원래의 값을 10으로 나눈 나머지 값으로 계산하였다. 예를 들어, 7,493이라는 숫자가 있을 때, ① 원래의 값 : 7,493, ② 원래의 값을 1,000으로 나눈 값 : 7, ③ (원래의 값을 100으로 나눈 값 - 10 * 원래의 값을 1,000으로 나눈 값) : 74 - 10 * 7 = 4 , ④ (원래의 값을 100으로 나눈 나머지를 다시 10으로 나눈 값) : 93 / 10 = 9, ⑤ 원래의 값을 10으로 나눈 나머지 값 : 3으로 계산 할 수 있었다. 계산 결과, 7,493 + 7 + 4 + 9 + 3 = 7,516이라는 값이 나오고, num[7516] 에 들어가는 값을 똑같이 하나 증가시켜 주었다.

원래 나눗셈을 진행하게 되면 소수점도 나와야 하는 것이 맞지만 변수를 정수형으로 선언하였기 때문에 소수점 아래 부분은 다 무시하고, 각 자리수는 단순히 몫과 나머지로 계산해 볼 수 있었다. 또한 각 자리수를 계산하게 되면 10,000을 초과하는 숫자들이 생길 수 있기 때문에 정수형 배열의 크기 또한 여유롭게 10,100 정도로 두었다. 마지막으로 셀프 넘버인 숫자를 출력해야 하는데, 배열에 들어가는 값이 한 번이라도 증가했다면 그 값은 생성자에 의해 만들어졌다고 볼 수 있기 때문에 배열에 들어가 있는 값이 0인 경우에만 숫자를 출력하도록 하였다. 그 결과, 셀프 넘버들을 찾아낼 수 있었다.

이 문제는 8달 전에 풀려고 시도했던 적이 있었는데 실패했었던 문제였다. 그 때 풀었던 소스코드를 다시 보니 코드 작성의 형태는 지금과 별 다를 바가 없었지만 조건 부분에서 각 자리 수를 구하는 과정이 잘못되어 있었다. 이제야 다시 풀게 되어서 기쁘지만 문제의 분류 자체가 함수로 되어 있어서 함수를 이용하여 푸는 방식도 한번 찾아봐야 할 것 같다는 생각이 든다.

Author

Alec J

Posted on

2018-04-06

Updated on

2021-02-09

Licensed under