[Greedy] 백준 10610번 “30” Python 풀이

문제 링크

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

풀이

• 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어한다.
  • 102에 포함된 숫자는 1, 0, 2이며, 30의 배수가 되는 가장 큰 수는 210(2, 1, 0)이다.
• 이 문제는 해당 수가 30의 배수가 되는 조건을 알아야 풀 수 있으며, 30의 배수가 되는 조건은 아래와 같다.
  • 일의 자리가 0이어야한다.
    • 따라서, 받은 숫자 내에 0이 없다면 -1을 출력해야한다.
  • 각 자리의 숫자들을 모두 더했을 때, 3으로 나누어 떨어져야한다.
    • 따라서, 받은 숫자들의 합이 3으로 나누어 떨어지지 않는다면 -1을 출력해야한다.
  • 두 조건을 통과했을 때, 주어진 숫자들을 내림차순 정렬한다면, 30의 배수가 되는 가장 큰 수가 만들어진다.

코드

import sys

# 양수 n을 문자열 형식으로 입력 받음
n = sys.stdin.readline().rstrip()

# 0이 존재하는지
zero = False
# 각 자릿수의 합
sum = 0

for num in n:

    # 0이 존재한다면
    if (int(num) == 0):
        zero = True
    # 각 자릿수를 더하기
    sum += int(num)

# 0이 존재하지 않는다면
if (zero == False):
    print(-1)
# 각 자릿수의 합이 3으로 나누어떨어지지 않는다면
elif (sum % 3 != 0):
    print(-1)
# 문제 없는 경우
else:
    # 각 자릿수를 내림차순 정렬한 뒤, 문자열로 변환
    print(''.join(sorted(n, reverse = True)))