10610번 : 30

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

10610번: 30

 

 

문제

 

 

코드

import java.util.Arrays;
import java.util.Collections;
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String n = sc.next();
		String arr[] = n.split("");
		int sum=0;
		
		for(int i=0;i<arr.length;i++)
			sum+=Integer.parseInt(arr[i]);
		
		if(n.indexOf("0")==-1 || sum%3!=0) {
			System.out.print(-1);
		}
		else {
			Arrays.sort(arr, Collections.reverseOrder());
			System.out.print(String.join("",arr));
		}
	}

}

 

 

해결방법

문제를 보고 어떻게 풀지 계속 생각을 해봤는데 반복문을 사용해서 모든 경우의 수를 찾는 방법밖에 떠오르지 않았다. 이 방법으로 푼다면 시간제한이 1초이기에 무조건 시간초과가 날 것이다. 한참을 생각하다 결국 다른 사람의 풀이를 참고하였다.

 

30의 배수가 되기위해서는 다음과 같은 조건을 만족하면된다.

1. 모든 숫자의 합이 3의 배수여야 한다.
2. 0이 존재해야한다.

이 조건을 만족하는 값은 30의 배수이다. 그러므로 입력받은 문자열이 위의 조건이 만족하는지 검사해보고 만족한다면 내림차순 정렬하여서 출력하면 30의 배수가 되는 가장  큰 수가 된다. 

배수 판별법만 알았다면 풀기 쉬웠을 것 같다. 

 

 

배수 판별법 

2의 배수 판별법: 일의 자리수가 0,2,4,6,8 이면 2의 배수이다.
3의 배수 판별법: 각 자리수의 합이 3의 배수이면 3의 배수이다.
4의 배수 판별법: 끝의 두자리 수가 00이거나 4의 배수이면 4의 배수이다.
5의 배수 판별법: 일의 자리수가 0,5 이면 5의 배수이다.
6의 배수 판별법: 짝수이고, 각 자리수의 합이 3의 배수이면 6의 배수이다.
8의 배수 판별법: 끝의 세자리 수가 000이거나 8의 배수이면 8의 배수이다.
9의 배수 판별법: 각 자리수의 합이 9의 배수이면 9의 배수이다.
30의 배수 판별법: 3의 배수이면서 0이 존재해야한다.