[BOJ/BaekJoon] 백준 10610 30 (Python / 파이썬)

BaekJoon BOJ 백준 10610 30 문제는 양수 N에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 구하는 문제로 그리디 알고리즘 유형의 문제이고 난이도는 Silver 5이다.

 

BaekJoon 10610 30 문제 정보

출처

- https://www.acmicpc.net/problem/10610

알고리즘 분류

- 그리디 알고리즘 (greedy algorithm, 탐욕법), 정렬(sorting), 문자열, 수학, 정수론 

난이도

- 실버 5 / Silver 5

 

30 문제 요약

• 어느 날, 미르코는 우연히 길거리에서 양수 N을 보았다.
  
• 길거리에서 찾은 수에 포함된 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만들고 싶어 한다.
• N을 입력받는다. N는 최대 105개의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.
• 미르코가 만들고 싶어 하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.
  

문제 풀이 과정

30의 배수가 되려면 3의 배수이면서 10의 배수(1의 자리가 0) 이어야 한다. 

3의 배수는 모든 자리 수의 합이 3의 배수이면 된다.

 

1. 양수 N을 입력받는다.
2. 각 자릿수의 합을 구한다.
3. 0이 들어있지 않으면 -1을 출력한다.
4. 각 자릿수의 합이 3의 배수가 아니면 -1을 출력한다.
5. 30의 배수이면 입력받은 N을 큰 수부터 오름차순 정렬하여 출력한다.

 

코드 및 설명 (풀이 1)

• num_list - 입력받은 N을 한 자리씩 원소로 담은 리스트
• add - 각 자릿수의 합

def thirty(num_list):
    if '0' not in num_list:  # 10의 배수가 아니면
        return -1

    # 각 자리 수의 합 구하기
    add = 0
    for num in num_list:
        add += int(num)

    if add % 3 != 0:  # 3의 배수가 아니면
        return -1

    # 30의 배수이면
    num_list.sort(reverse=True)  # 오름차순 정렬
    return int(''.join(num_list))


print(thirty(list(input())))

코드 및 설명 (풀이 2)

• num - 입력받은 N
• num_count - 0~9의 수의 개수를 저장한 리스트
• sum - 각 자릿수의 합
• cnt - 수(0~9)의 개수

num = input()
num_count = [0] * 10
sum = 0

for i in range(10):
    cnt = num.count(str(i))
    num_count[i] = cnt  # 0~9의 수의 개수를 저장
    sum += num_count[i] * i  # 각 자리 수의 합

if num_count[0] == 0:  # 10의 배수가 아니면
    print(-1)
elif sum % 3 != 0:  # 3의 배수가 아니면
    print(-1)
else:  # 30의 배수이면
    for i in range(10):
        print(str(9 - i) * num_count[9 - i], end='')  # 큰 수부터 출력

---

 

BaekJoon 백준 BOJ 10610 30 문제를 파이썬 python으로 풀어보았다. 그리디 알고리즘 유형의 문제로 난이도는 Silver 실버 5이다.