백준 10610번 30

아래는 문제의 링크입니다. JAVA를 사용했습니다.

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

10610번: 30

문제의 설명은 아래와 같습니다.

문제를 요약하면 다음과 같다.

1. 숫자를 입력받는다.
2. 입력받은 숫자를 조합해 30의 배수가 되는 가장 큰 수를 만든다.

처음에 제일 중요하게 생각한 것은 숫자를 조합해 30의 배수인 수를 체크하는 것이었다.

근데 입력을 보니까 10^9..? 아무래도 문자열로 입력을 받아야 한다고 느꼈다.

그러고 생각을 해보니 엄청 긴 문자열을 사용해 30인 배수인 수를 조합하고 그것들의 최댓값을 찾으라?!

뭔가 이상함을 느꼈다. 그래서 30인 배수의 조건을 찾아보기로 했다.

 

첫 번째는 일의 자리 숫자가 0인 것이다.

두 번째는 힌트를 얻어서 알았다. 숫자의 모든 자릿수의 합이 3의 배수면 그것은 3의 배수라는 것이다.

예를 들어 15, 21, 33, 39 모두 각 자릿수를 더하면 그 값이 3의 배수라는 것을 알 수 있다. 그러므로 15, 21, 33, 39는 3의 배수다.

 

정리하면 정렬을 통해 일의 자리 숫자가 0이고, 모든 자릿수의 합이 3의 배수면 30의 배수다.

그러므로 max를 두고 최댓값을 찾을 필요가 없다.

 

소스코드는 아래와 같다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String str = br.readLine();
        String[] arr = str.split("");

        int sum = 0;
        for (String s : arr) {
            sum += Integer.parseInt(s);
        }

        if(!str.contains("0") | sum % 3 != 0){
            System.out.println(-1);
        }

        else{
            Arrays.sort(arr,Comparator.reverseOrder());
            for (String s : arr) {
                System.out.print(s);
            }
        }

    }
}

 

이상으로 포스팅을 마칩니다. 감사합니다.