[Baekjoon Online Judge] 10610번: 30

10610번: 30

요구사항

 - 양수 N이 주어진다.
 - 양수 N에 포함되어 있는 숫자들을 섞어 30의 배수가 되는 가장 큰 수를 만든다.

입력

 N을 입력받는다. N는 최대 10의 5제곱의 숫자로 구성되어 있으며, 0으로 시작하지 않는다.

출력

 미르코가 만들고 싶어하는 수가 존재한다면 그 수를 출력하라. 그 수가 존재하지 않는다면, -1을 출력하라.

---

 30의 배수가 되기 위해서는 각 자리수의 합이 3으로 나누어 떨어져야 하고, 적어도 하나의 0이 포함되어야 한다. 30의 곱을 확인해보면 쉽게 규칙을 찾아 낼 수 있다.

 

30 x 0	0	30 x 10	300, 3 + 0 + 0 = 3
30 x 1	30, 3 + 0 = 3	30 x 11	330, 3 + 3 + 0 = 6
30 x 2	60, 6 + 0 = 6	30 x 12	360, 3 + 6 + 0 = 9
30 x 3	90, 9 + 0 = 9	30 x 13	390, 3 + 9 + 0 = 12
30 x 4	120, 1 + 2 + 0 = 3	30 x 14	420, 4 + 2 + 0 = 6
30 x 5	150, 1 + 5 + 0 = 6	30 x 15	450, 4 + 5 + 0 = 9
30 x 6	180, 1 + 8 + 0 = 9	30 x 16	480, 4 + 8 + 0 = 12
30 x 7	210, 2 + 1 + 0 = 3	30 x 17	510, 5 + 1 + 0 = 6
30 x 8	240, 2 + 4 + 0 = 6	30 x 18	540, 5 + 4 + 0 = 9
30 x 9	270, 2 + 7 + 0 = 9	30 x 19	570, 5 + 7 + 0 = 12

 

 각 자리수를 더하고, 입력 받은 숫자 list에 0이 포함되어 있으면 30의 배수라고 가정하고, 정렬하여 가장 큰 순서로 수를 만들어 준다.

 

 만약 0을 포함하지 않거나 3으로 나누어 떨어지지 않는다면 30의 배수가 아니기 때문에 -1을 출력하여 마무리한다.

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Baekjoon10610 {

    public static void main(String[] args) throws IOException {

        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));

        String number = bufferedReader.readLine();
        List<Integer> list = new ArrayList<>();

        int total = 0;
        for (int i = 0; i < number.length(); i++) {
            total += number.charAt(i) - '0';
            list.add(number.charAt(i) - '0');
        }

        Collections.sort(list);

        if (list.contains(0) && total % 3 == 0) {
            for (int i = list.size() - 1; i >= 0; i--) {
                bufferedWriter.write(String.valueOf(list.get(i)));
            }
        } else bufferedWriter.write("-1");

        bufferedWriter.flush();
        bufferedReader.close();
        bufferedWriter.close();
    }
}

 

 

해당 문제를 조합으로 해결한다면 N은 10의 5제곱 만큼의 자리수를 가지고 있기 때문에 오랜 시간이 걸릴 것으로 예상된다. 적당한 규칙을 찾아서 풀이를 해보는 편이 낫다고 판단한다.