파이썬 알고리즘 239번 | [백준 10610번] 30

239. 30

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

<내 풀이>

from itertools import permutations
import sys
n = int(sys.stdin.readline().rstrip())
n = list(str(n))

chk = 0
zero = False

for e in n : # (+) 각 자릿수의 합을 구한 것 
    chk+=int(e)
    if int(e)==0 :
        zero = True # 0이 존재하면 zero 를 참으로 체크

if chk%3!=0 : 
    # 각 자릿수의 합이 3으로 나눠떨어져야 30의 배수 가능 
    print(-1)
    exit(0)

if zero==False : 
    # 그리고 맨 마지막이 0 으로 끝나야 하기 때문에 0 이 항상
    # 입력받은 수 안에 0 이 있어야 함 
    print(-1)
    exit(0)
        
n.sort(reverse=True)
lis = permutations(n)

totallis =[]
for i in lis :
    cand = int("".join(i))
    if cand%30==0 :
        totallis.append(cand)
        print(totallis[-1])
        break
if len(totallis)==0 :
    print(-1)
    exit(0)

< 내 틀렸던 풀이, 문제점>

2%에서 시간초과

from itertools import permutations
import sys
n = int(sys.stdin.readline().rstrip())
n = list(str(n))
lis = permutations(n)
totallis =[]
for i in lis :
    cand = int("".join(i))
    if cand%30==0 :
        totallis.append(cand)
if len(totallis)==0 :
    print(-1)

else : 
    totallis.sort()
    print(totallis[-1])

10%에서 시간초과

from itertools import permutations
import sys
n = int(sys.stdin.readline().rstrip())
n = list(str(n))
n.sort(reverse=True)
lis = permutations(n)
totallis =[]
for i in lis :
    cand = int("".join(i))
    if cand%30==0 :
        totallis.append(cand)
        print(totallis[-1])
        break
if len(totallis)==0 :
    print(-1)

<반성 점>

• 30으로 나눠떨어지는 규칙을 찾지 못한 점이 아쉽
  규칙은 아래와 같다

따라서 이 문제는 어떠한 규칙을 찾아야 한다고 생각했다.

 

우선 30의 배수가 되려면 마지막 수가 0이어야 하고,

3의 배수는 각 자리수들을 더한 값이 3으로 나누어떨어져야 하기에 다음과 같은 두 가지 규칙을 찾을 수 있다.

 

1. 마지막 수가 0이어야 한다.

2. 각 자리수들을 더한 값이 3으로 나누어 떨어져야 한다.

출처 : https://ongveloper.tistory.com/114

<배운 점>