[Baekjoon, Python] 10610번 : 30

도입

백준 알고리즘 분류-그리디 알고리즘 열 번째 문제이다.

백준 10610번 문제, 입력, 출력

---

백준 10610번 입출력 예제 1, 2, 3, 4

---

그리디 알고리즘

 그리디 알고리즘(탐욕 알고리즘)이란, 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다. 

 

 특징 - 1. 최적성의 원리 : 주어진 문제에 대한 최적해가 분할된 부분 문제의 최적해로 구성된다는 원리.

        - 2. 최적 해 보장 불가 

        - 3. 효율성 개선

 

그리디 알고리즘 예시 : 거스름돈 최소 동전 수

그리디 알고리즘 수행절차

 1. 해 선택 : 부분 해 집합에 추가 다음 항목 선택

                현재 상태 최적화 기준 만족 여부 확인

 2. 적합성 검증 : 새로운 부분 해 집합 조건 여부 확인

                      현재 집합이 해가 될 가능성 검사

 3. 해 검증 : 신규 구성 집합이 해인지 검사

                문제가 아니면 1번으로 돌아가서 반복

---

풀이

1. 30배수가 가지는 의미가 무엇인지 알 필요가 있다. 30은 2 x 3 x 5이다. 30배수라는 것은 2의 배수이기도 하고 3의 배수이기도 하고 5의 배수이기도 하다는 의미이다. 배수 판정법이라고 있다. 

 - 2의 배수 판정법 : 일의 자리가 0, 2, 4, 6, 8이다.

 - 3의 배수 판정법 : 모든 자리수를 더해서 3으로 나누어 떨어져야 한다.

 - 5의 배수 판정법 : 일의 자리가 0, 5이다. 

이 3가지 판정법을 전부 충족하려면 일의 자리가 0이여야 하고 모든 자리수를 더해서 3으로 나누어 떨어져야 한다는 뜻이다. 

2. 숫자를 입력 받으면 내림차순으로 정렬을 한다. 그리고 일의 자리가 0이고 모든 자리수를 더해서 3으로 나누어 떨어진다면 30의 배수라고 볼 수 있다. 3의 배수 판정법의 조건 때문에 입력받은 숫자를 내림차순으로 정렬해도 된다.  

---

코드

from sys import stdin

var_N = list(input())  # 0 < N <= 10^5
sorted_var_N = sorted(var_N, reverse=True)
sum = 0

for i in sorted_var_N:
    sum += int(i)

if sum %3 != 0 or '0' not in sorted_var_N:
    print(-1)
else:
    print(''.join(sorted_var_N)) 

---

마무리

 오랜만에 풀어본 그리디 알고리즘 30배수인지를 어떻게 판단할 것인지 결정하는 문제.