[그리디/수학] 백준 10610번 30 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

10610번: 30

 

 

2. 문제 풀이

 주어진 수를 재배열해서 가장 큰 30 배수를 만드는 문제입니다.

 

2022.01.26 - [Algorithm] - [Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

[Algorithm] 탐욕적인 그리디 알고리즘, 직관적이고 쉬운 문제해결

 30의 배수 조건은 '각 자릿수의 합이 3의 배수이면서, 1의 자리가 0'이어야 합니다. 즉, 각 자릿수의 합이 3의 배수이고, 0이 포함되어 있으면 재배열해서 30의 배수로 만들 수 있습니다.

 가장 큰 30의 배수를 만들어야 하니, 그리디 알고리즘대로 높은 자릿수부터 큰 숫자로 채우면 됩니다.

 

 

 

3. 코드

N = input()

#모든 자릿수를 더한 수가 3의 배수이면서 일의 자리가 0
digit_sum = 0
zero = False
for i in N:
    digit_sum += int(i)
    if i == '0':
        zero = True

#30의 배수가 맞다면
if digit_sum % 3 == 0 and zero:
    print("".join(sorted(list(N), reverse=True)))

#30의 배수가 아니라면
else:
    print(-1)

 각 자릿수의 합이 3의 배수이고, 0이 포함되어 있는지 확인합니다. 만약 아니라면 30의 배수가 될 수 없으니 -1를 출력합니다.

 30의 배수가 될 수 있다면, 각 자릿수를 내림차순으로 정렬한 뒤 출력합니다.

 

 

"".join(sorted(list(N), reverse=True))

 위 코드는 내림차순으로 문자열을 정렬한 다음에, ""(공백없이) 합쳐줍니다.