[PS] BOJ10610 30 ( Math ) with JAVA

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

10610번: 30

 

◎ 문제풀이 

 

입력으로 주어진 수로 만들 수 있는 30의 배수중 가장 큰 값을 구하는 문제이다. 30은 3x10이므로  30의 배수는 항상 뒤가 0으로 끝난다. 그러므로 30의 배수란, 뒤가 항상 0으로 끝나는 수 중 3의 배수가 되는 수를 의미한다. 그럼 3의 배수가 되는 수를 어떻게 구할까? 여기서 중학교 1학년 때 배운 개념이 사용될거라고는 생각도 못했다. 

 

배수 판정법을 이용하면 된다. 어떤 수의 각 자리의 숫자의 합이 3의 배수이면 그 수는 3의 배수라는 규칙이 존재한다. 이를 3의 배수 판정법이라고 하는데 ,아래 포스팅에 잘 정리되어 있다. 

 

2, 3, 4, 5, 6, 7, 8, 9, 11, 13의 배수 판정법

 

3의 배수판정법을 몰라서 주어진 수로 나올 수 있는 모든 경우의 수를 DFS로 탐색해서 %3이 0이 나오는 경우를 찾는 방식으로 풀었다가 메모리 초과가 발생했다. 알고보니 이런 수학적 지식을 사용하는 문제였다. 

 

 

◎ 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;

//BOJ10610 30
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] charArr = br.readLine().toCharArray(); // 입력받기
        Integer[] numArr = new Integer[charArr.length]; // 각 자리 수의 배열
        int sum = 0; // 각 자리 숫자의 합
        
        // 각 자리수 숫자를 정수형 배열로 저장
        for(int i=0;i<numArr.length;i++){
            numArr[i] = charArr[i] -'0'; 
            sum += numArr[i]; // 동시에 각 자리 숫자의 합도 계산
        }

        Arrays.sort(numArr, Comparator.reverseOrder()); // 내림차순 정렬 

        if(numArr[numArr.length-1] != 0 || sum%3 != 0){ // 끝이 0으로 끝나지 않거나 각 자리 숫자의 합이 3으로 나누어지지 않는다면 -1 출력
            System.out.println(-1);
        }else{ // 30의 배수인 경우, 결과 출력
            StringBuilder sb = new StringBuilder();
            Arrays.stream(numArr).forEach(sb::append);
            System.out.println(sb.toString());
        }
    }
}