[알고리즘]백준 10610번: 30

알고리즘 유형: 그리디 알고리즘

 

문제

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

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

입력

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

출력

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

 

풀이

---

시간압박이 조금 있었던 문제였습니다 

입력으로 받은 숫자를 정렬을 진행해주고, 약분이 되게 만들어주는건 뒤의 자릿수를 통해 결정되므로 

permutation을 통해 섞어주었다. 

 

이때 숫자가 30으로 약분이 되면 배열에 넣어주고 그 중 최댓값을 출력합니다 

 

import sys
from itertools import permutations
num = sys.stdin.readline().strip()

num= sorted(num,reverse=True)
i=2
# print(int("".join(num)))
if int("".join(num))%30!=0:
    i=3
    possible=[]
    
    front, back = num[:len(num)-i], num[len(num)-1-i:]
    front_num = "".join(front)
    for tail_nums in permutations(back,i):
        for tail_num in tail_nums:
            front_num +=tail_num 
        
        if int(front_num)%30 ==0: 
            possible.append(int(front_num))
   
    if len(possible)!=0:
        print(max(possible))
    else:
        print(-1)
else:
    print(int("".join(num)))