[백준] 10610번 30 - Python / 알고리즘 중급 1/3 - 그리디 알고리즘 (연습)

---

---

---

💡 문제

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

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

입력

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

출력

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

---

💭 접근

이 문제를 해결하기 위해서 꼭 알아야 하는 것이있다.

바로 3의 배수인 수의 각 자리의 합 또한 3의 배수라는 것인데, 아래와 같이 증명할 수 있다.

만약 123이라는 숫자가 주어졌다고 가정해보자.

먼저 10의 거듭제곱 수(10$^k$)를 3으로 나눈 나머지는 반드시 1이다.

$10^k \mod 3 = 1$

따라서 분배법칙에 의하면,

$123 \mod 3 = (1 \times (100 \mod 3) + 2 \times (10 \mod 3) + (3 \mod 3)) \mod 3$

이 되는데, 이를 정리하면,

$123 \mod 3 = (1 + 2 + 3) \mod 3 = 6 \mod 3 = 0$

이므로 123은 3의 배수인 것을 알 수 있다.

따라서 이 문제를 해결하기 위해선, 먼저 30의 배수를 만들 수 있는 지 확인하기 위해 입력받은 숫자를 내림차순으로 정렬한다.

이후, 가장 작은 수가 0이 아니라면 30은 3과 10의 곱이기 때문에 30의 배수를 만들 수 없다.

만약 가장 작은 수가 0이라면 각 숫자들의 합을 구한 후 3으로 나누어 떨어진다면, 0을 제외한 나머지 수르 어떻게 배열하든 3의 배수가 되므로 30의 배수를 만들 수 있다.

---

📒 코드

n = sorted(list(map(int, input())), reverse=True)

if 0 not in n or sum(n) % 3 != 0:
    print(-1)
else:
    print(*n, sep='')

---

💭 후기

3의 배수를 판별하는 방법만 알고 있었다면 쉽게 해결할 수 있는 문제.

---

🔗 문제 출처

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

---