백준 10610번 30 [배수 판정법] :: 마이구미

이번 글은 백준 알고리즘 10610번 "30" 을 다뤄본다.

이 문제는 배수 판정법을 활용해서 문제를 해결할 수 있다.

일단 먼저 문제를 보자.

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

미르코를 도와 그가 만들고 싶어하는 수를 계산하는 프로그램을 작성하라. (그 수가 존재한다면)

주어지는 수에 대해 섞은 모든 경우에서 30의 배수가 되는 가장 큰 수를 찾는 문제다.

예를 들어보자.

120과 210이 30의 배수이지만 가장 큰 수는 210이기 때문에 정답은 210이다.

이 문제를 배수판정법을 통해 해결해보자.

3의 배수 판정법에 의하면, 모든 자리 수의 합이 3의 배수이다.

이것이 의미하는 바가 무엇인가 확인해보자.

각 자리수의 합이 3의 배수라면, 그 수는 3의 배수라는 것을 알 수 있다.

이 증명을 활용하여 문제를 해결할 수 있다.

또한 문제는 30의 배수이기 때문에 하나의 조건을 더 추가해주어야한다.

0이 무조건 존재해야한다는 것이다.

그로 인해, 우리는 30의 배수가 아닌 경우를 찾을 수 있다.

각 자리의 수의 합이 3의 배수가 아니거나 주어진 수에 0이 포함되어있지 않을 경우이다.

if (sum % 3 != 0 || array[0] == 0) {
    System.out.println(-1);
    return;
}

전체 소스는 아래 Github URL을 참고하길 바란다.

백준 알고리즘 10610번 "30" 전체 소스 

https://github.com/hotehrud/acmicpc/blob/master/math/10610.java