[백준] 10610번: 30

문제

백준 - 10610번: 30

분석

N이 주어졌을 때, 수의 배열을 조정해서 30의 배수중 가장 큰 수를 만들어내고, 만약 그런 수를 만들지 못하면 -1을 출력하는 문제이다.

N이 최대 10^5로 구성되어 있으므로, 각자리 수를 조합해서 모든 가능한 수를 만들어 각각 30의 배수인지 판단하는 것은 시간초과에 걸릴 것이다.

30의 배수라는 것은 10의 배수이기도, 3의 배수이기도 하다.
먼저, 10의 배수는 끝에 무조건 0이 온다. 따라서 끝에 0이 없으면 10의 배수가 아니다.
3의 배수는 각 자리수의 합이 3인지를 보면 된다. 이게 가능한 이유를 다음에서 설명한다.

만약에 abc라는 세자리 숫자가 있다고 하면 이 수는 a X 100 + b X 10 + c 로 표현할 수 있다.
이를 조금 변경하면 a X (100 -1 + 1) + b X (10 -1 +1) + c = (99a + 9b) + (a+b+c) 이 된다.
(99a + 9b)는 3의 배수이므로 각 자리수의 합인 (a+b+c)를 구하여 이것이 3의 배수이면 전체가 3의 배수임이 증명된다.

따라서 n을 내림차순 리스트로 입력받아서 끝자리가 0이 아니거나 각 자리의 합이 3의 배수가 아닐경우 -1을 출력하고, 그렇지 않으면 join을 이용해서 출력하면 된다.
내림차순으로 하는 이유는 숫자가 가장 크고 30의 배수인지는 if문을 통해 걸러지기 때문이다.

코드

해결언어 : Python

import sys
input = sys.stdin.readline

n = sorted(list(map(int, list(input().rstrip()))), reverse=True)
if n[-1] != 0 or sum(n)%3 != 0:
    print(-1)
else:
    print(''.join(map(str, n)))

끝으로..

각 자리수의 합으로 배수 판정을 하는 것을 배웠다.