취미로 코딩하기

네 자리 정수(leading zero 포함) K에 다음과 같은 연산을 반복하면 어떻게 될까?

1. K의 각 자리로 이루어진 가장 큰 수 K1과 가장 작은 수 K2를 구한다.
2. K1과 K2의 차를 구해 새로운 K로 한다.

위 연산에 대해 단순히 추측해보면, K는 (비둘기집의 정리에 의해) 일정 주기로 같은 순서를 반복하게 될 것이라고 기대할 수 있다.

하지만 네 자리 정수에 한정하면 더욱 강력한 특징이 있다. 바로, K의 모든 자릿수가 동일(1111 등)하지 않다면 K는 7번 이하의 연산을 적용하면 항상 6174가 된다는 것이다.

위의 연산은 Kaprekar's routine이라고 불리는 연산이다. 그리고 (모든 자릿수가 동일하지 않은) 각 자리 수에 대하여 Kaprekar's routine을 반복 적용했을 때 최종적으로 나올 수 있는 수를 Kaprekar's constant라 한다. 이와 같은 이름은 이러한 개념을 탐구한 인도의 수학자 D. R. Kaprekar의 이름에서 따왔다.

세 자리 수에도 마찬가지로 네자리 수의 6174와 같은 수가 존재한다. 바로 495이다. 임의의 (모든 자릿수가 동일하지 않은) 세 자리수로 시작해 Kaprekar's routine을 반복 적용하면 그 세자리수는 6번 이하의 연산을 적용하면 항상 495가 된다.

Kaprekar's constant는 모든 자릿수에 대해 항상 존재할까? 아쉽지만 그렇지는 않다. 예를 들어, 다섯자리 수의 경우 Kaprekar's routine을 적용하다보면 각 수는 (53955와 59994를 반복하는 사이클), (61974, 82962, 75933, 63954를 반복하는 사이클), (62964, 71973, 83952, 74943을 반복하는 사이클)의 세 가지 사이클중 하나로 수렴하게 된다.

Kaprekar's routine은 세 자리 수와 네 자리 수를 한 가지 수로 수렴시키는 재미있는 특징이 있고 그 과정이 단순해 코딩 입문자들에게 구현 예제로 추천할만한 주제 중 하나이다. 관심이 있다면 아래의 문제를 해결해보자.

https://www.acmicpc.net/problem/9047 

위 문제의 풀이는 다음 글에 적어두었으니 관심이 있다면 읽어보자.

이 글은 다음 글을 참조하여 작성하였다. 더 많은 정보를 알고싶다면 다음 글을 읽어보자:

https://en.wikipedia.org/wiki/Kaprekar%27s_routine