[python/백준/분할정복] 10610 : 30

문제

풀이

처음에는 아래처럼 숫자의 조합을 나열해, 30의 배수가 되는 가장 큰 숫자를 찾았다.

#-------------------풀이 ---------------------
## 시간초과로 오류났다.

n = list(str(int(input())))

# n으로 만들 수 있는 가장 큰 수, 가장 작은 수 
max_n = sorted(n,reverse=True)  
max_n = int(''.join(max_n)) 

min_n = sorted(n)  
min_n = int(''.join(min_n)+ '0'*min_n.count('0')) 

# max_n보다 크거나 같은 30의 배수 
max_n = (30*(max_n//30)+(max_n%30)*30)

# min_n보다 크거나 같은 30의 배수 
min_n = (30*(min_n//30)+(min_n%30)*30)

for i in range(max_n, min_n-1, -30):
    if sorted(list(str(i))) == sorted(n):            
        print(i)
        exit(0)
print(-1)

하지만 이 방법으로 하니 시간초과로 오류가 났다.

정말 아무리 생각해도 방법을 모르겠어서 백준에 질문하기 게시판에 들어갔다.
다들 근데 숫자의 조합을 생각하지 않아서 의아했다. 근데 고민 끝에 알았다.

30의 배수는 자리수를 다 더해서 3의 배수가 되고, 맨 끝 자리가 0이면 된다.
따라서 이 조건에 맞는 숫자의 조합을 갖고 있다면, 30의 배수가 되는 가장 큰 수는
양수 N의 숫자의 조합의 최댓값일것이다!!

코드

#-------------------풀이2 (정답!) ---------------------

# 30의 배수 : 자리 수를 다 더해서 3의 배수가 되고, 맨 끝 자리가 0이면 된다.

n = input()
n_sum = sum(list(map(int,n))) # 자리수의 합 
n_max= int(''.join(sorted(n,reverse=True))) # 숫자 조합의 최댓값 

# 3의 배수가 아니라면 -1 
if n_sum%3:
    print(-1)
else:
    # 맨 끝 자리가 0이 아니라면 -1 
    if n_max%10:
        print(-1)
    else:
        print(n_max)

후기

그리디 재밌다.