[BOJ] 배수 판정법과 백준 10610 Python

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

10610번: 30

미르코라는 분이 30을 존경해서 길거리에 찾은 수를 가지고 30의 배수가 되는 가장 큰 수를 만들고 싶다고 하신다.

input 은 숫자하나로 들어오고 이 숫자의 자릿수를 이리저리 옮겨서 나오는 수가 30의 배수이고 그 중에 가장 큰 수여야 한다.

그러면 이 문제를 보고 숫자들을 섞어가면서 30으로 나누었을때, 가장 큰 수를 출력하면 되지 않을까? 라고 생각하지만

'시간초과' 를 맞이하게 될 것이다. 그러면 어떻게 풀어야 될까?

바로 배수 판정법을 이용하는 것.

https://ko.wikipedia.org/wiki/%EB%B0%B0%EC%88%98_%ED%8C%90%EC%A0%95%EB%B2%95

배수 판정법 - 위키백과, 우리 모두의 백과사전

배수 판정법은 어떤 수 n이 있다면 그 수의 배수가 가지는 특징을 가지고 판정을 하는 법인데, 생각보다 알고리즘 문제에서 단골로 등장한다. 

---

배수 판정법

2 4 6 8 10 12 14 16 18 20 22...  

2의 배수들은 일의자리 수가 2 4 6 8 0 이 반복되는 패턴을 가지고 있다. 수학적으로 간단히 생각해 볼때, 2의 배수이자 자릿수가 바뀌는 10 부터 2를 계속 더하면 2 4 6 8 0 이 될 수 밖에 없다. 

그렇다면 3은?

3 6 9 12 15 18 21 24 27 30 33 36 

자릿수가 두 개인 숫자들 만 봤을 때, 3 6 9 3 6 9가 반복된다.
이것에 대한 증명은 예를 들어 369라는 3의 배수가 있다고 한다면 이를 3x100 + 6x10 + 9 x 1로 나눠서 전개할 수 있고

이를 또 다시 전개한다면

3 x ( 99 + 1 ) + 6 x ( 9 + 1) + 1 x (1) 로 전개 할 수 있다. 이때 369를 n,m,k로 치환한다면 

n x ( 99 + 1 ) + m x ( 9 + 1) + k x (1) = 99n + n + 9m+ m + k

이때, 99, 9  => 10^k -1 은 3의 배수인 것을 이용해  나머지  n+m+k가 3의 배수이면 그 수는 3의 배수인 것을 알 수가 있다.

---

 

이런 식으로 43가지의 배수 판정법이 있고 이를 이용해 위 문제를 풀어보겠다. 30의 배수 판정법은 다음과 같다.

3의 배수 판정법과 10의 배수 판정법을 응용하면 된다. 10의 배수 판정법은 초등학생도 알 것 같으니 패스했다.

3의 배수 판정법은 각 자릿수를 더해서 3이 나오면 되니 가장 큰 수를 구하는 법도 쉬워졌다. 그냥 큰 수대로 정렬하면 되기 때문이다.

그래서 처음에 3과 10의 배수 판정법을 응용하여 30의 배수가 될 수 있는지 판정하고 그 숫자의 자릿수를 sort하면 쉽게 풀릴 것 같다.

import sys

number = sys.stdin.readline().strip()
number_list = [int(s) for s in number]

if not "0" in number or sum(number_list) % 3 != 0:
    print(-1)
else:
    number_list.sort(reverse=True)
    print("".join(str(s) for s in number_list))