[Python] 백준 10610 : 30

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

10610번: 30

첫번째 시도

import itertools
numb = list(input())
#만들 수 있는 수 중에서 30의 배수, 그 중에서도 가장 큰 수를 만들어야 한다.
#만들지 못하면 -1 출력!
numb.sort(reverse=True)
nPr = itertools.permutations(numb, len(numb))
for num in list(nPr):
    if int(''.join(num)) % 30 == 0:
        print(int(''.join(num)))
        exit(0)
print(-1)

당연히 메모리 초과가 날 줄 알았고... 역시 메모리 초과 이슈가 있었다. 하나하나 경우의 수를 만들어서 판단하는 과정이 매우 비효율적이다.

 

ANS

N = list(input())
N.sort(reverse=True)
sumV = 0
for idx in N:
    sumV += int(idx)
if sumV % 3 != 0 or "0" not in N:
    print(-1)
else:
    print(''.join(N))