백준 | 10610 - 30 (python)

3️⃣ 30

숫자들을 조합해서 30의 배수를 만들어야 한다.

3의 배수 특징을 알게 된다면 더 쉽게 풀 수 있는 문제였다. (몰라서 중간에 포기했었다..)

 

 

---

✏️ 문제

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

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

 

입력

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

 

출력

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

 

 

---

💡 해결방법

시간 초과한 방법

숫자의 배열에 0이 없다면 30의 배수가 될 수 없으므로 -1을 출력한다. 만약 0이 있다면 0을 제외한 모든 수를 큰 수부터 배열한 뒤 3의 배수가 된다면 0을 붙여 출력한다.

-> 숫자가 크다면 정렬해야하는 시간이 길어서 초과함

 

어떻게 하면 해결할 수 있을지 고민하다가 3의 배수 특성을 찾게 되었다. 모든 숫자의 합이 3의 배수라면 그 수는 3의 배수라는 특징이 있다. 즉, 숫자에 0이 있을 경우 모든 숫자의 합이 3의배수라면 숫자를 가장 큰 수부터 정렬했을 때의 값은 3의 배수이다.

만약 0이 없다면 -1을 출력한다.

0이 있을 경우 모든 숫자를 합한 뒤 3의 배수라면 가장 큰 수부터 정렬하고 출력하고 3의 배수가 아니라면 -1을 출력한다.

숫자가 3의 배수가 아니라면 그 수는 어떻게 배열을 해도 3의 배수가 될 수 없다. 즉 배열에 0이 포함되어 있을 때 숫자의 합이 3의 배수일 경우 가장 큰 값은 큰 수부터 정렬했을 때의 값이 될 수밖에 없다.

 

 

👩🏻‍💻 소스코드

import sys
n = list(map(int,sys.stdin.readline().rstrip().strip()))

if 0 not in n:
    print(-1)
else:
    if sum(n) % 3 == 0:
        n.sort(reverse=True)
        a = ''.join(map(str, n))
        print(a)
    else:
        print(-1)

 

 

---

 

 

10610번: 30