[백준 10610 파이썬] 30 (실버5, 그리디)

알고리즘 유형 : 그리디
풀이 참고 없이 스스로 풀었나요? : O

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

소스 코드(파이썬)

import sys
input = sys.stdin.readline

N = input().rstrip()

if "0" in N and sum(map(int, N)) % 3 == 0:
    print("".join(reversed(sorted(N))))
else:
    print(-1)

풀이 요약

1. 3의 배수 결정 조건이 핵심이다. 어떤 수에 대해, 각 자리 수의 합이 3의 배수이면 그 수는 3의 배수이다.

2. 만약 어떤 수가 3의 배수라고 하자. 그리고 그 수에 0이라는 수가 어떤 자리에 포함되어 있다고 하자. 이 0을 맨 오른쪽으로 옮기면 대충 xxxxxx0 형태일 것이다. 그런데 모든 자리 수의 합이 3의 배수이므로, 이 수는 3의 배수이다. 0은 합에 포함이 안되므로, 0을 제외한 나머지 부분도 3의 배수인데, 3의 배수에 10을 곱한 것은 30의 배수가 된다. 즉, 이 수의 각 자리 수를 모두 내림차순으로 정렬하면, 문제의 답인, 30의 배수이면서 최대인 수가 된다.

배운 점, 어려웠던 점

• 수학적 지식이 있어야 그리디 풀이가 보이는 문제였다.