[백준 10610 : PYTHON] 30

문제 풀기 : 10610번

10610번: 30

문제

길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수 만든다.

단, 수가 존재하지 않으면 -1을 출력한다.

문제풀이

최적의 해를 구하는 그리디 문제이다.

숫자들의 위치를 바꿔서 30의 배수가 되는 수 중 가장 큰 수를 찾으면 된다.

30의 배수가 되려면

첫째, 마지막 자리수가 0이어야 한다.

둘째, 3의 배수는 각 자리의 숫자 합이 3으로 나누어 떨어진다.

코드 TIP

''.join(배열) : 배열을 문자열로 바꾼다.

sorted(변수, reverse=True) : 변수(문자열, 리스트 등)를 내림차순으로 정렬시킨다.

전체코드

# n : 입력받을 숫자
n = input()

# 숫자에 0이 없으면 30의 배수가 아니다.
if '0' not in n:
    print(-1)
else:
    sum = 0
    for i in n:
        sum += int(i)
    if sum % 3 == 0:
        # 내림차순 정렬
        print(''.join(sorted(n,reverse=True)))
    else:
        print(-1)