백준 9047번 6174 [카프리카 수] :: 마이구미

이번 글은 백준 알고리즘 문제 9047번 "6174" 를 다뤄본다.

문제는 단순히 수학 문제로써, "카프리카 수" 에 관련된 문제가 된다.

9, 45, 55, ( ), 297, 703 에서 ( ) 안에 들어갈 수는?

최근 영재 발굴단 방송에서 문제를 푼 최연소 이태호(10살) 군을 주제로 방영되었다. (답은 99)

카프리카 수를 알고 있다면, 쉽게 해결할 수 있는 문제이다. (카프리카 수)

보자마자 메모하여 관련 알고리즘 문제를 발견하여 다룰 수 있게 되었다.

9047번 문제는 아래와 같다.

간단한 연산이지만 Kaprekar 는 이 연산이 놀라운 결과를 보여준다는 것을 발견했다. 올해 연도인 2008 로 그 결과를 알아보자. 2008 로 만들 수 있는 가장 큰 수는 8200 이고 가장 작은 수는 0028 이다. 

• 8200 – 0028 = 8172 
• 8721 – 1278 = 7443 
• 7443 – 3447 = 3996 
• 9963 – 3699 = 6264 
• 6642 – 2466 = 4176 
• 7641 – 1467 = 6174 
• 7641 – 1467 = 6174 

6174 에 도달한 다음에는 매번 6174 를 만들어 낸다. 2008 만이 유독 6174 에 도달하는 것이 아니라 한 숫자로 이루어지지 않은 모든 네 자리 수는 Kaprekar 연산을 통해 6174 로 가게 된다. 2008 의 경우 6 단계를 거쳐 6174 로 가게 되었는데, 다른 숫자가 입력으로 주어졌을 때 몇 단계만에 6174 로 가는지 알아내는 프로그램을 작성하시오. 

카프리카 수에 대한 개념만 이해한다면 쉽게 해결할 수 있다.

아래 2개의 링크만 참조해도 충분하다. 어렵지 않다.

• 카프리카 수 - 영재 발굴단에서 나온 문제를 해결할 수 있다.
• 카프리카 상수 - 9047번 문제를 해결할 수 있다.

문제를 풀기 위한 카프리카 수를 만드는 방법은 아래와 같다. (자세한 건 링크를 참조하는 것이 좋다)

• 숫자 하나로만 이루어지지 않은 4자리 숫자를 정한다. (예: 1000은 인정하되, 1111은 인정하지 않는다.) 첫 자리에 0이 와도 무방하다.
• 이 숫자를 크기 순으로 배열하여 두 수를 만든다. 하나는 큰 순, 하나는 작은 순으로 배열한다.
• 큰 쪽에서 작은 쪽을 빼 준다. 이때 나온 0은 유지한다.

위에서 언급했듯이 문제를 풀 때 주의할 점은 0을 유지해야한다.

이해하기 위한 예로 1000을 보자.

1000으로 만들 수 있는 가장 큰 수는 1000, 가장 작은 수는 1이 된다.

무작정 1000 - 1을 빼면 문제를 풀 수 없다.

1000 - 1 = 999 => 999 - 999 로 카프리카 수를 만들 수 없다.

주의해야할 점은 4자리 숫자를 유지하고, 0을 유지해야한다.

즉, 1000 - 0001 => 0999 이 되어야한다.

그래야 위 과정을 진행할 수 있다.

1000 - 0001 = 0999
9990 - 0999 = 8991
9981 - 1899 = 8082
8820 - 0288 = 8532
8532 - 2358 = 6174

코드의 설명은 생략하겠다.

단순히 네자리 숫자에 대해 가장 큰 수와 가장 작은 수를 만들어 두 수를 빼는 과정을 반복한다.

구현에 있어서, 많은 방법이 있겠지만, 결론적으로 구현의 난이도가 낮기 때문에 설명을 생략한다.

충분히 카프리카 수를 이해했다면, 구현이 가능할 것이라고 생각한다.

전체 소스는 Github URL을 참고하길 바란다.

백준 9047번 6174 전체 소스 Github URL

https://github.com/hotehrud/acmicpc/blob/master/math/9047.java