[백준] 10610번 : 30 - Python

최근 그리디 알고리즘을 보고 있습니다 ..

아마 다른 분들께는 기본 중에 기본일텐데 .. 저한테는 아직 많이 낯선것 같습니다 ...

그래도 홧팅 ~!

 

문제

 

 

풀이

처음에 해당 문제를 접근한 방법은 다음과 같았습니다.

 

1. 입력 받은 수를 리스트로 저장하여 각 자리수를 분리한다.

2. 각 배열의 인덱스를 int 형으로 변경한다.

3. 그 배열안의 수들을, 순열을 사용하여 순서가 있게 조합한다.

4. 조합한 것들 중 30의 배수가 되는 가장 큰 숫자를 출력한다

 

코드로 나타내면 ..

 

import sys, os, io, atexit
from itertools import permutations

input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n = list(input())

max = 0

#각 자리 수를 정수 형태로 만들어줌
for i in range(len(n)):
    n[i] = int(n[i])

arr = list(permutations(n,len(n)))

result = []
index = 0
for i in arr:
    number = len(i)
    temp=0
    for k in range(number):
        temp += i[k]*(10**k)
    result.append(temp)
    index += index



for i in result:
    if i%30==0:
        if max<i:
            max = i


if max == 0:
    print(-1)
else:    
    print(max)

 

그런데 .. 결과는 .. 메모리 초과 ㅠㅠ

너무 무지성으로 풀었나봅니다 .. 

 

검색해보니, 해당 문제는 3의 배수만이 가지는 조건,

 

해당 수의 모든 자릿수의 합이 3의 배수가 되면 된다.

 

를가지고 풀어야한다고 합니다 !

 

추가적으로 문제에서는 30의 배수라고 했으니, 숫자 내에 0이 없다면 30의 배수가 될 수 없습니다 !

 

코드

import sys, os, io, atexit


input = lambda: sys.stdin.readline().rstrip('\r\n')
stdout = io.BytesIO()
sys.stdout.write = lambda s: stdout.write(s.encode("ascii"))
atexit.register(lambda: os.write(1, stdout.getvalue()))

n = list(input())

sum = 0
check = 0
result = 0
index = 0
#각 자리 수를 정수 형태로 만들어줌
for i in range(len(n)):
    if n[i] == '0':
        check = 1
    sum += int(n[i])

if check != 1:
    print(-1)
elif sum % 3 != 0:
    print(-1)
else:
    n.sort(reverse=True)
    print(''.join(n))