백준 10610. 30

문제 : 30

문제

입력받은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

입력

N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

풀이

간단한 문제인데 자바로 알고리즘 시작하면서 입력값 범위 생각하고, 그에 따른 시간복잡도를 생각하다보니 괜히 쓸데없이 시간을 좀 썼었는데, 아침에 일어나서 보니 5분만에 뚝딱 해결책이 바로 생각났다.

입력받은 숫자로 조합한 숫자가 30의 배수가 되는 가장 큰 수를 만들고 싶어한다. 30의 배수라는 것은 3의 배수이면서 10의 배수라는 점이다.
그렇다면 3의 배수의 특징을 알고있어야 한다.
3의 배수는 모든 자리의 수를 다 더한 값이 3의 배수가 되면 된다.
즉 이번 문제에서 이 특징을 활용하려면 각 자리의 숫자들을 다 더해서 3으로 나눠떨어지는지 확인하면 되는 것이다.

10의 배수는 마지막 자리수가 0이 되면 된다.

내림차순으로 입력받은 값을 정렬해주었다. 각 자리 숫자의 합이 3의 배수인지만 확인하면 되기 때문에 숫자의 위치를 고려할 필요는 없다. 321의 3+2+1 이나 123의 1+2+3은 둘 다 같기 때문이다.
위 조건을 만족하면서 마지막 자리수가 0이면 30의 배수이다.
혹시 입력이 00000으로 들어올 경우도 있다고 생각해서 자리수의 합이 0이 되는 상황 또한 처리해주었다.

python 파이썬 풀이

n = list(map(int, input()))
n.sort(reverse= True)
s = sum(n)
if s % 30 == 0 and sum != 0:
    for i in n:
        print(i, end="")
else:
    print(-1)