10610번 백준 30

30 실패다국어

한국어   

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

36535

14345

11355

38.831%

문제

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

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

 

입력

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

출력

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

 

 

첫번째풀이 메모리초과 오류

 

from itertools import permutations

num=int(input(""))

num_list=[]

count=0

for i in str(num):

    num_list.append(i)

   

per_num=list(permutations(num_list,len(num_list)))

per_num.sort(reverse=True)

for i in per_num:

    n=int(''.join(i))

    if n%30==0:

        print(''.join(i))

        count+=1

        break

   

if count==0:

    print("-1")

   

 

 

   

 

   

   

permutations 순열을 써서 메모리오류가 뜬거같다 ...

 

 

인터넷에서 힌트를 얻은결과 !

 

Tip

30의 배수판별법

각각 숫자의 대한 배수를 판별하는 방법이 있었다. 이것을 배수판별법이라고 부른다. 나는 처음 보는 공식(?)이기도 했다.

30의 배수판별법은

• 일의 자리가 무조건 0이여야 한다.
• 각각 자리마다의 숫자를 다 더하고 3을 나눠 나누어 떨어져야 한다.
• 360을 예로 들어보자.
  
  1. 일의 자리가 0이므로 통과
  2. 3 + 6 + 0 = 9
  3. 9 / 3 = 3 (나누어 떨어짐)
  4. 360은 30의 배수이다.

 

이 팁을 이용하여 문제를 풀이하였다.

 

num=list((input("")))

num.sort(reverse=True)

sum=0

for i in num:

    sum+=int(i)

   

 

if "0" not in num or sum%3!=0:

    print("-1")

else:

    print(''.join(num))

 

 

일의자리는 무조건 0이여야하며

각자리를 더한수는 3으로 나누어떨어져야

30의배수판별에 적합하다.

 

 

왜 이걸몰랐지...