백준알고리즘 - 10610번 30 - 파이썬(Python)

문제

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

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

 

입력

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

 

출력

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

 

예제 입력과 출력

 

 

알고리즘 분류

그리디 알고리즘

정수론

 

정답

 

n=input()
a=[]

for i in range(len(n)):
    a.append(int(n[i]))

a.sort(reverse=True)

b=0
c=''

if a[-1] == 0:
    a.pop()

    for j in range(len(a)):
        b= b+a[j]
        
    if b % 3 == 0:
        a=list(map(str,a))

        for k in range(len(a)):
            c=c+ a[k]
              
        print(int(c) * 10)      
        
    else:
        print(-1)

else:
    print(-1)

*3의 배수의 특징은 각 자릿수를 모두 더하고 3으로 나눴을 때 나눠 떨어지면 3의 배수라는 점입니다.

30 → 3+0=3 , 3 ÷ 3=1

102 → 1+0+2, 3 ÷ 3=1

2931 → 2+9+3+1=15, 15 ÷ 3=5

80875542  → 8+0+8+7+5+5+4+2=39, 39 ÷ 3=13

 

이를 이용해 30의 배수가 되는 수를 구했습니다.

30의 배수이려면 3의 배수이면서 숫자 0이 들어가 있는지 확인했습니다.

 

for문을 통해 양수 n을 한자리씩 구분해 a라는 리스트에 넣고 내림차순으로 정렬해줍니다.

 

if문을 통해 리스트 a의 마지막 수( a[-1])가 0인지 확인했습니다.
마지막 수를 확인한 이유는 리스트 a를 내림차순으로 정렬했기 때문입니다.

 

리스트 a에 숫자 0이 있다면 이를 지우고 리스트의 값들을 b에 더했습니다.

 

b의 값을 3으로 나눴을 때 나눠 떨어지는지 확인하여 이에 속하면 리스트 a의 값들을 int형에서 str형으로 바꿔주었습니다.

그리고 리스트 a의 값을 str형으로 c에 더해주었습니다.

c를 int형으로 바꾸고 아까 제외한 10을 곱해주어 결과를 출력해주었습니다.

 

30의 배수가 되는 가장 큰 수를 만들어야 해서 리스트 a를 내림차순으로 정렬하고 3의 배수의 특징을 이용해
답을 구했습니다. (어차피 3의 배수라면 각 숫자의 자리는 상관없으니까 가장 큰순서로 출력하기 위해 정렬!!)

 

---

백준 알고리즘 10610번 : https://www.acmicpc.net/problem/10610

10610번: 30