어떤 양의 정수 n은 [n+reverse(n)]의 모든 숫자가 홀수로만 이뤄지는 속성이 있다. 예를 들어, 36+63=99이고 409+904=1313이다. 이런 숫자를 가역숫자(reversible number)라 한다. 36과 63, 409와 904는 가역숫자이다. 0으로 시작하는 경우는 n, reverse(n)에 허용되지 않는다.
1천 이하에는 120개의 가역숫자가 있다.
10억(109)이하에는 몇 개의 가역 숫자가 있는가?
--------------------------------------------------------------------------
문제에서 0으로 시작하는 경우를 허용하지 않는다고 했으므로, 끝이 0인 숫자는 가역 여부를 확인할 필요가 없다. 프로그램의 구성은 비교적 간단한데, 10억까지 계산을 해야되기 때문에 시간이 많이 소요된다. 이것을 줄일 방법이 있는지 모르겠지만 일단 시도해 봤다.
10억까지 반복하면서, 각 숫자의 순서를 바꾸고 더해서, 모든 자릿수가 홀수인지 확인하면 된다. 10이하의 숫자는 무조건 짝수가 되기 때문에 고려하지 않았다. 1억까지 구하는데 10분 넘는 시간이 걸렸고, 숫자가 커지면서 조금씩 시간이 늘어나 10억까지는 100분 넘게 걸려 답을 구할 수 있었다.
가만히 생각해 보니, 10이하 숫자를 고려하지 않았던 것처럼, 9자리 숫자도 n+reverse(n)을 하면 모두 홀수가 되지 않는다. 가운데인 5번째 숫자는 같은 숫자를 2번 더하기 때문에 무조건 짝수가 되고, 그것을 막으려면 6번째 숫자가 10이 넘어야 한다. 그러면 4번째 숫자도 10이 넘어서, 7번째 숫자가 홀수이면 3번째 숫자도 홀수인 경우 4번째 숫자에서 1이 넘어오기 때문에 (3번째와 7번째) 둘 중 하나는 짝수가 될 수 밖에 없다. 그러다보니, 전체 연산시간의 90% 이상을 차지하는 1억 이상의 숫자 모두가 가역숫자가 되지 못하는데 계산하느라 시간을 낭비한 꼴이 되어버렸다.