백준(BAEKJOON): 셀프 넘버(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
3
5
7
9
20
31
42
53
64
 |
 |       <-- a lot more numbers
 |
9903
9914
9925
9927
9938
9949
9960
9971
9982
9993

• 출처 ICPC > Regionals > North America > Mid-Central Regional > 1998 Mid-Central Regional Programming Contest D번

해설

이번 문제는 접근하는 방식이 좀 틀려 먹은 듯하다. 코딩 결과가 마음에 들지 않는다. 문제를 읽고 먼저 떠오른 게 아래 두 가지다.

1) 배열을 쓰지 말자.
2) 이것은 수학 문제가 분명하니 셀프 넘버를 찾는 간단한 공식이 있을 것이다.

배열을 쓰지 말자는 생각을 왜 했는지 모르겠다. 2)를 찾는다면 자연수 N이 셀프 넘버인지 여부는 바로 결정될 것이므로 메모리 아깝게 굳이 배열을 쓸 필요가 없다는 판단이었을지 모르겠다. 사실 1)은 2)에 비하면 별 문제가 아니었다. 이건 노가다 문제가 아닐 거야. 분명 간단한 해법이 있을 거라고 생각했다. 자연수 N이 셀프 넘버인지 간단히 찾아낼 수 있는 방법이나 공식(에라토스테네스의 체 같은 거 말이다.)이 있을 것이란 생각에 고민하느라 진이 빠지고 말았다. 지금에 와서는 내가 찾지 못했을 뿐 분명 해가 있을 거라고 오기를 부리고 싶다. 사실 문제를 풀고 이 문제를 해법을 구글링한 것은 내 오기가 합리적인 추측이었다고 스스로를 위로하기 위함이었다. 하지만 ….
이래 저래 궁리한 것이라곤 D(N)을 다시 풀어 쓰는 방식이다. 이 문제에서 1 ~ 10,000 사이의 셀프넘버를 찾기에 이 범위 안의 생성자는 아래와 같이 표현할 수 있다. 최고 10000 이하의 수는 천의 자리의 생성자를 갖게 되므로 자연수 N은 klml(0 < k, l, m, n < 9)으로 표현된다. 이를 십진수 표기법으로 바꾸면, 1000k + 100l + 10m + n이 되는 것이다. 이 수를 D(x) 안 에 넣으면 결국 k + l + m + n + 1000k + 100l + 10m + n가 된다. 식을 간단히 정리하면 아래가 된다.

D(X) = 1001k + 101l + 11m + 2n

아무런 의미가 없는 바꿔 쓰기이다. 이 하나의 식만으로는 해를 구할 방법이 없다. 자연수 X의 자리수가 늘어날수록 변수의 개수만 늘어날 뿐이다. 결국 노가다만 남았을 뿐이다.

소득은 없었지만 고민한 시간이 아까워 어찌됐든 저 식을 사용하기로 한다. 어떤 수 testNum이 들어오면 저 식의 변수(k, l, m, n)를 일의 자리부터 순차적으로 돌려서 나온 값 sum이 testNum과 같은지를 확인하면 될 듯하다. 같다면 testNum은 최소한 1개 이상의 생성자를 가진 수이므로 더이상 for문을 돌 이유가 없으므로 goto문을 이용해 for문을 완전히 빠져 나와 버린다. 같지 않은 경우의 testNum만을 화면에 출력한다.

소스코드: C

#include <stdio.h>
int main(int argc, char *argv[])
{
    int k, l, m, n;
    int testNum = 1;
    int sum = 0;

    while (testNum <= 10000) {
        for (k = 0; k < 10; ++k) {
            for (l = 0; l < 10; ++l) {
                for (m = 0; m < 10; ++m) {
                    for (n = 0; n < 10; ++n) {
                        sum = 1001*k+101*l+11*m+2*n;
                        if (testNum == sum)
                            goto EXIT;
                    }    
                }
            }
        }
        printf("%d\n", testNum);
EXIT:
        testNum++;
        sum = 0;
    }
    return 0;
}

결과는 문제의 부합하므로 채점 결과는 맞았습니다!!다. 그런데 4개의 중첩 for문을 도느라 생각 외로 실생시간이 꽤 길다. 채점표에서는 40ms로 표시된다.
이렇게 한번 코딩을 하고 나서 서두에 말했던 간단한 식이 있으리라는 기대로 다른 사람들의 코드를 찾아보았다. 기대했던 그런 건 없었다. 그제서야 이 문제가 '함수'로 분류된 문제였음을 깨닫는다. 어차피 노가로 풀 문제였다면 루프롤 좀 덜 돌릴 방법을 찾았어야 했다. 굳이 배열을 쓰지 않겠다고 고집할 문제도 아니었고 말이다. 배열만 써도 한번의 루프로 해결될 문제인데…. 게다가 문제의 취를 생각하면 배열이나 노가다를 염두해 둘게 아니라 함수 정의에 신경을 썼어야 했다. 때늦은 후회다. 그저 반면교사로 삼길 바라며!