백준 10610번 파이썬 풀이: 30

백준 10610번 30

 

알고리즘 분류: 수학, 정렬, 정수론

 

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

 

10610번: 30

문제

어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다. 미르코는 30이란 수를 존경하기 때문에, 그는 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라.

입력

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

출력

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

 

 

문제 파악

 

주어지는 입력 값으로 가장 큰 30의 배수를 만드면 되는 문제이다.

 

30의 배수가 될 수 없는 경우에는 -1을 출력하면 된다.

 

이 문제의 핵심은 30의 배수를 어떻게 찾아내냐는 것인데 이것은 정수의 배수 판정법을 알아야 한다.

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

30의 배수는 3의 배수이면서 10의 배수이기도 해야한다.

 

10의 배수가 되기 위해선 마지막 일의자리가 반드시 0으로 끝나야 하므로 입력값에 0이 없다면

 

30의 배수가 될 수 없기 때문에 바로 -1을 출력해주면 된다.

 

3의 배수가 되기 위해선 각 자리수의 합이 3의 배수이면 3의 배수이다.

 

 

코드

# 10610번

n = input()

if "0" not in n:
    print(-1)

else:
    num_sum = 0
    for i in range(len(n)):
        num_sum += int(n[i])

    if num_sum % 3 != 0:
        print(-1)
    
    else:
        sorted_num = sorted(n, reverse=True)
        answer = "".join(sorted_num)
        print(answer)

앞서 말했듯이 0이 들어가지 않는 수는 10의 배수가 될 수 없기 때문에 바로 -1을 출력한다.

 

0이 들어간다면 10의 배수는 충족하기 때문에 3의 배수인지를 확인해야 한다.

 

각 자리수를 다 더해서 3의 배수인지 확인하고 그렇지 않으면 -1을 출력한다.

 

만약 3의 배수라면 이 수는 30의 배수가 될 수 있는 수이기 때문에

 

30의 배수가 되는 가장 큰 값을 출력해야 한다.

 

30의 배수가 되는 가장 큰 값은 그냥 이 수를 내림차순으로 정렬해주면 된다.

 

어차피 일의 자리수만 0이면 30의 배수가 될 수 있는데 0보다 작은 수는 존재하지 않으므로

 

내림차순으로 정렬해주면 30의 배수이면서 가장 큰 수가 된다.