백준 10610. 30

tose33 2022. 1. 2. 10:44

10610번: 30

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

www.acmicpc.net

30 = 2 x 3 x 5

따라서 30이 되는 조건은 2의 배수 and 3의 배수 and 5의 배수

2의 배수: 1의 자리수가 짝수여야 한다.

3의 배수: 각 자리수의 합이 3의 배수여야 한다.

5의 배수: 1의 자리수가 0 or 5 여야 한다.

위의 세 조건을 동시에 충족하려면

일단 3의 배수 조건을 충족하려면 각 자리수의 총합이 3의 배수여야 하고,

2,5의 배수 조건을 충족하려면 5의 배수 조건에 의해 1의 자리가 0 or 5여야 하는데, 0,5중 짝수는 0뿐이므로

1의 자리가 0이어야 한다.