백준 10610번 파이썬 풀이 | 30 | 그리디(Greedy) 알고리즘

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

10610번: 30

<<문제>>

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

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

 

입력

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

 

출력

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

 

 

 

<<문제 풀이>>

처음에 문제를 풀때, 조건을 자세히 읽지 않고 순열로 풀었다. 계속 시간 초과가 나서 문제를 다시 정확히 읽어보니 10의 5승의 N을 순열로 풀기에는 당연히 무리라고 생각이 들었다.... 

(만약 N이 크지 않았다면, 순열로 자른것들을 내림차순으로 정렬한 후 30으로 나눌때 가장 큰거 찾으면 됨)

 

따라서 문제를 간단하게 다시 풀었고 결국, 30의 배수는 0이 문장에 포함되어야 있어야 하며 3으로 나눠 떨어져야 한다.

 

*   ''.join(N)은 N을 이어 붙이는데 ""안에 있는것을 추가로 붙여준다. 여기서는 아무것도 없으므로 N의 값들이 합쳐진다.

 

예시) ['1','2'] ==> 12

 

 

<<소스코드>> 

N= input() temp=0 # 0 이 없으면 -1 if '0' not in N:      print(-1) else:      for i in N:           temp+=int(i)      if temp%3 != 0: # 3의 배수가 아니면           print(-1)      else:            print("".join(sorted(N,reverse=True)))