[파이썬] 백준 알고리즘 No.10610 30

백준 10610번 30 문제

 

 

 

이 문제를 보자마자, 아 permutation을 써서 나올 수 있는 모든 경우의 수중 30으로 나누어 떨어지는 수의

최대 값이 정답이겠구나! 라는 생각이 들어 코드를 짜보았으나.. 결과는 시간초과였다.

 

최초 코드의 시간 초과

 

from itertools import permutations
n = input()
data = []

for i in permutations(n, len(n)):
    tmp = int("".join(i))
    if tmp % 30 == 0:
        data.append(tmp)

if data:
    print(max(data))
    exit()

print("-1")

 

시간 초과가 된 코드는 바로 이것인데, 순열의 경우의 수가 10^5 까지 간다면, 그만큼 시공간 복잡도의 수가 기하급수적으로 늘어나게 됨을 간과하였다.

 

 

 

 

 

문제를 다시 곰곰히 살펴보니, 30의 배수가 되는 가장 큰 수 를 만들라는게 제일 큰 힌트였다.

 

30의 배수 -> 3의 배수 이면서 10의 배수.

결국 최대 값이면서, 맨 오른쪽 끝이 0으로 끝나야하니

입력받은 값을 역순으로 정렬하여 그 값이 30으로 나누어 떨어지기만 하면 되는 것이다.

 

n = list(input())
n.sort(reverse = True)
n = int("".join(n))
if n % 30 == 0:
    print(n)
else:
    print("-1")

수정 후 정답 코드

이렇게 쉽게 풀수 있었던 걸 너무 고전하였던 것 같다.

문제를 잘 읽어보는 습관을 들이자.