백준 10610. 30 / 배수판정법

🅰 백준 10610. 30

✏️ 문제 풀이

• 자리수가 10^5개 이다. 100000의 정수가 아니라 00000000000000000000000000000000000000000000000000 개의 숫자가 들어간다는 말이다.
• int나 long 형으로 처리할 수 없기 때문에 문자열로 처리해야 한다.
• 30의 배수가 되기 위해서는 자리수의 합이 3의 배수여야 하고, 마지막 자리가 0이여야 한다.
• ans에 정렬하여 출력하려고 했으나 숫자 자리수가 10^5이므로 int,long의 자리수를 훌쩍 넘기므로 배열or 문자열로 출력해야 했다.
• 오름차순으로 배열이 정렬되어 있으므로, 배열의 역 순서대로 출력을 해주었다.

✏️ 소스코드

package greedy;

import java.util.*;
import java.io.*;

public class Main_실버5_10610_손은성 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String st = br.readLine();
		int n[] = new int[st.length()];
		int ans = 0;	//모든 자리 수 합 
		for (int i = 0, end = st.length(); i < end; i++) {
			n[i] = st.charAt(i) - '0';
		}
		Arrays.sort(n);
		
		//모든 자리 수 합 구하기 - 3의 배수인지 확인하기 위함
		for (int i = 0,end = st.length(); i < end; i++) {
			ans += n[i];
		}
		
		// 첫 시작이 0인가? && 자리수 합이 3의 배수인가?
		if(n[0] == 0 && ans%3 == 0) {
			// 맞다면 전체 자리수 배열 역순서대로 출력
			for (int i = n.length-1; i >=0; i--) {
				System.out.print(n[i]);
			}
		}else
			System.out.println(-1);
	}
}

 

✅ 후기

• 30의 배수를 어떻게 구하는지에 대해서도 고민을 많이 했다. 모든 수를 더해서 30의 배수라는걸 알았는데 그 이상의 조건은 생각해내기 힘들었다.
• 최소공배수의 조건을 만족시키면 되기 때문에 2의배수, 3의배수, 5의배수의 조건을 충족하는 마지막 자리수가 0이고 모든 수의 합이 3의 배수인 것을 중심으로 해서 문제를 풀었다.
• 실버 5따위가 너무 어렵다.

 

************************************배수 판정법 참고용**************************************

• **1**의 배수는 모든 수이기 때문에 판별할 필요가 없다.
• **2**의 배수는 모든 짝수이다. 즉, 일의 자리가 0, 2, 4, 6, 8인 수이다.
• **3**의 배수는 각 자리 숫자의 합이 3의 배수인 수이다.
• **4**의 배수는 가장 끝에 두 자리수가 00이거나 4의 배수인 수이다. (십의 자리가 짝수인 경우에는 일의 자리수가 0, 4, 8이고 십의 자리수가 홀수인 경우에는 일의 자리수가 2, 6이면 된다.)
• **5**의 배수는 일의 자리수가 홀수면 5, 짝수면 0인 수이다.
• **6**의 배수는 2와 3의 공배수, 즉, 짝수이면서 각 자리의 합이 3의 배수인 수이다.
• **7**의 배수는 일의 자리를 두 배하고 나머지 수를 빼는데 결과가 0 또는 7의 배수인 수이다.(스펜스의 방법) 다른 방법으로는 일의 자리부터 세 자리씩 끊어서 교대로 빼고 더한 것이 7의 배수일 경우 본래의 수도 7의 배수이다. 이 방법은 7이 1001의 약수임을 이용한 것으로 다른 1001의 약수 11, 13, 77, 91, 143, 1001에도 적용시키는 게 가능하다. 또 다른 방법으로는 본래의 수를 10으로 나눈 뒤에 소수점 아래는 버림한 값에 본래의 수의 일의 자리를 다섯 배한 수를 더한 결과가 7의 배수이면 본래의 수도 7의 배수이다.
• **8**의 배수는 가장 끝에 세 자리수가 000이거나 8의 배수인 수이다. (좀 더 쉽게 설명하자면 백의 자리가 0이거나 짝수인 경우에는 끝에 두 자리수가 00, 08, 16, 24, 32, 40, 48, 56, 64, 72, 80, 88, 96 다시 말해 8의 배수인 수이고, 백의 자리가 홀수인 경우에는 끝의 두 자리수가 4의 배수면서 8의 배수가 아닌 두 자리수 4, 12, 20, 28, 36, 44, 52, 60, 68, 76, 84, 92이어야 한다.)
• **9**의 배수는 각 자리 숫자의 합이 9의 배수인 수이다.
• **10**의 배수는 일의 자리가 0인 수이다.
• **11**의 배수는 홀수 자리의 합과 짝수 자리의 합의 차가 0이거나 11의 배수인 수이다. 다른 방법은 일의 자리 숫자를 제외한 후 남은 숫자에 제외시킨 일의 자리 숫자를 뺀 결과가 0이거나 11의 배수이면 본래의 수도 11의 배수이다.
• **12**의 배수는 3과 4의 공배수인 수이다.
• **13**의 배수는 일의 자리를 네 배하고 나머지 자리에서 더한 값이 13의 배수인 수이다. 다른 방법으로는 일의 자리부터 세 자리씩 끊어서 교대로 빼고 더한 것이 13의 배수일 경우 본래의 수도 13의 배수이다.
• **14**의 배수는 2와 7의 공배수 즉 일의 자리를 두 배하고 나머지 수를 뺐을 때 결과가 0 또는 7의 배수인 수이면서 동시에 짝수인 수이다.
• **15**의 배수는 3과 5의 공배수인 수이다. 즉 다시 말해 각자리의 합이 3의 배수이면서 일의 자리가 0 또는 5인 수이다.
• **16**의 배수는 끝에 네 자리수가 0000이거나 16의 배수인 수이다. 다른 방법은 끝에 네 자리의 앞의 두 자리 (천의 자리와 백의 자리) 를 n으로 놓고 그 수를 4로 나눈 나머지에다 4를 곱해서 나머지 수에 더한다 이 값이 0이거나 16의 배수이면 원래 수도 16의 배수이다.
• **17**의 배수는 일의 자리를 다섯 배 하여 나머지 자리에서 뺀 값이 0이거나 17의 배수인 수이다.
• **18**의 배수는 2와 9의 공배수 즉 각 자리의 합이 9의 배수이면서 짝수인 수이다.
• **19**의 배수는 일의 자리를 두 배하고 나머지 수를 더하는데 그 결과가 19의 배수인 수이다.
• **20**의 배수는 십의 자리가 0, 2, 4, 6, 8이고 일의 자리가 0인 수이다. 또는 끝의 두 자리가 00이거나 20의 배수인 수를 말한다.
• **21**의 배수는 3과 7의 공배수인 수이다. 즉 각 자리의 합이 3의 배수이면서 7의 배수로 판정되는 수이다. 다른 방법으로는 일의 자리를 두 배 하고 나머지 수를 빼는데 결과가 0 또는 21의 배수일 경우 본래의 수도 21의 배수이다.
• **22**의 배수는 2와 11의 공배수인 수이다. 다시 말해 짝수이면서 홀수 자리의 합과 짝수 자리의 합의 차가 0이거나 11의 배수인 수.
• **23**의 배수는 일의 자리 숫자를 7배하여 나머지 자리를 더한 값이 23의 배수인 수이다.
• **24**의 배수는 3과 8의 공배수인 수이다.4와 6의 공배수이기도 하지만 4 와 6의 최소공배수가 아니기 때문에 4와 6의 배수 판별법이 섞일수 없다.
• **25**의 배수는 끝의 두 자리가 00, 25, 50, 75인 수이다.
• **26**의 배수는 2와 13의 공배수인 수이다.
• **27**의 배수는 4자리 이상일 경우에는 9의 배수의 확장 개념으로 37의 배수와 비슷하게 일의 자리부터 세 자리씩 나눠 묶은 후 그 숫자들을 모두 더한 값이 27의 배수인 수이다. 1001이 7, 11, 13의 배수인 것과 비슷하게 999가 27, 37의 배수인 것처럼 말이다. 다른 방법으로는 일의 자리 숫자를 8배 하여 나머지 자리에서 뺀 값이 27의 배수면 본래의 수도 27의 배수이다.
• **28**의 배수는 4와 7의 공배수인 수이다.
• **29**의 배수는 일의 자리 숫자를 3배하여 나머지 자리에서 더한 결과가 29의 배수인 수이다.
• **30**의 배수는 3의 배수이면서 일의 자리가 0인 수이다.
• **31**의 배수는 일의 자리를 3배하고 나머지 자리에서 뺀 값이 0 또는 31의 배수인 수이다.
• **32**의 배수는 마지막 다섯 자리가 00000이거나 32의 배수인 수이다.
• **33**의 배수는 3과 11의 공배수인 수이다. 다시 말해 각 자리의 합이 3의 배수면서 짝수자리의 합에서 홀수자리의 합을 뺀 값이 0이거나 11의 배수인 수이다. 다른 방법으로는 두 자리 씩 끊어서 더한 값이 33의 배수일 경우 본래의 수도 33의 배수이다.
• **34**의 배수는 17의 배수이면서 짝수인 수이다.
• **35**의 배수는 일의 자리가 0이거나 5이면서 7의 배수인 수이다.
• **36**의 배수는 4와 9의 공배수인 수이다.
• **37**의 배수는 27의 배수와 마찬가지로 일의 자리부터 세 자리씩 나눠 묶은 후 그 숫자들을 모두 더한 값이 37의 배수인 수이다. 이 방법도 역시 37이 999의 약수라는 것을 이용했으며, 111, 333, 999에도 적용할 수 있다. 단, 9와 3은 각 자리숫자의 합이기 때문에 해당이 되지 않는다. 다른 방법으로는 일의 자리를 11배하여 나머지 자리에서 뺀 값이 0 또는 37의 배수인 수이다.
• **38**의 배수는 19의 배수이면서 짝수인 수이다.
• **39**의 배수는 3의 배수이면서 13의 배수인 수이다.
• **40**의 배수는 일의 자리가 0이고, 백의 자리와 십의 자리가 4의 배수인 수이다.(출처 : 위키백과)