[백준] 10610 in Python : 시간초과를 위해 Greedy를 떠올리자

1. 첫번째 시도.. 시간초과난다 

 

from itertools import permutations

n = list(input())
result = -1
cases = permutations(n, len(n))

for case in cases:
    if case[0] == '0':
        continue
    else:
        num = ''
        for i in case:
            num += i
        num = int(num)
        if num%30 == 0:
            result = max(result, num)
print(result)

 

if 문에서 30의 배수가 아닌 조건을 걸러주면 된다 !! 

우선 30의 배수를 떠올려 보면 30, 60, 90, 120, 150, 180, 210 ...

0 으로 끝나는 것을 알 수 있다!! 

또한 '3'의 배수의 성질인 각자리 숫자 합이 3의 배수여야 한다 

 

그렇게 else 를 통과한 것들은 모두 30의 배수라는 뜻인데, 숫자를 내림차순으로 정렬하면 가장 큰 숫자를 바로 구할 수 있다 

조건을 만족하는 후보들 중에서 가장 큰것! -> 바로 여기서 Greedy 접근을 해야하는 것이다 

n = list(input())
total = 0

for i in n:
    total += int(i)
if '0' not in n or total %3 != 0:
    print(-1)
else:
    n.sort(reverse=True)
    print(''.join(n))

+ 문자열 합칠 때는 join()함수가 역시 유용하다