[BOJ] 10610번 | 30 (Python3)

🔗문제 보러가기

10610번: 30

 

 

문제 설명

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

 

---

입력

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

 

---

출력

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

 

---

예제 입출력

 

---

풀이 전략

정수론에 대한 지식이 부족해서 한 번 알아봤었습니다. 11 이상의 수에 대해서는 정보가 별로 없더군요.
그래서 3의 배수와 10의 배수 판별법을 이용하여 풀어 보았습니다.

 

필요한 지식

3의 배수 판별법

각 자릿수의 합이 3의 배수이면 그 수는 3의 배수가 됩니다. 예를 들어 80875542 라는 수를 판별해봅시다.

8 + 0 + 8 + 7 + 5 + 5 + 4 + 2 = 39        # 39는 3의 배수

 

10의 배수 판별법

이건 잘 아실 겁니다. 일의 자리 수가 0이면 됩니다.

310  # 10의 배수

 

해결 전략

• 주어진 수를 이루는 숫자들 중에 0이 없다면 10의 배수 조건을 충족할 수 없으므로 -1 출력
• 주어진 수의 각 자릿수들의 합이 3의 배수가 아니라면 3의 배수가 아니므로 -1 출력
• 위 두 경우가 아니라면, 내림차순 정렬한 숫자가 30의 가장 큰 배수

---

소스 코드 및 결과

N = input()
numbers = []
sumNum = 0

for charNum in N:
    intNum = int(charNum)
    numbers.append(int(intNum))
    sumNum += intNum

if (0 not in numbers) or (sumNum % 3 != 0):
    print(-1)
    exit()
    
numbers.sort(reverse = True)         # 내림차순 정렬
result = "".join(map(str, numbers))  # 정수 리스트 -> 문자열 변환
print(result)

 

역시 수학 지식 기반이 튼튼해야 알고리즘 생각도 잘하나 봅니다. (저는 부족하다는 의미입니다.)

저보다 2배 빠른 속도를 자랑하는 분의 코드를 살펴보니, 0 ~ 9 까지의 각 숫자의 개수를 카운트하셨네요.

역시 남의 코드 보면서 코드 리뷰하는 것도 재밌습니다. 다양한 생각들을 보며, 저보다 뛰어난 사람들을 보고 배울 게 많으니까요.