[JAVA 알고리즘] 재미있는 수학

The digits 3 and 9 share an interesting property.
If you take any multiple of 3and sum its digits, you get another multiple of 3.
For example 3 * 118 = 354 and 3 + 5 + 4 = 12, which is a multiple of 3.

Similarly, if you take any multiple of 9 and sum its digits, you get another multiple of 9.
A digit that is interesting in one base(진법) is not necessarily interesting in another base.
For example, 3 is interesting in base 10(10진법) but uninteresting in base 5(5진법).
Question. Given an int base, your task is to return all the interesting digits for that base in increasing order.

 

한글 번역

숫자 3과 9는 재미있는 성질이 있습니다. 3의 배수의 각 자릿수의 합은 다른 3의 배수가 됩니다.

예를 들어 3 * 118 은 354 이고 3 + 5+ 4 = 12 는 3의 배수입니다.

유사하게 9의 배수의 각 자릿수의 합은 9의 배수가 됩니다.

 

어떤 진법에서 이러한 성질을 갖는다고 다른 진법에서 이러한 성질을 가지지는 않습니다. 예를 들어 3은 10진법에서 이러한 성질을 가지지만,

5진법에서는 성립하지 않습니다.

문제: base 진법(int)이 주어졌을 때 이러한 성질을 가진 수를 오름차순으로 리턴하세요.

====================================================================================================

풀이법

 

모든 경우의 수를 따지기 보다 수학적으로 생각하면 금방 풀리는 문제이다.

간단하게도 base 가 주어졌을 때 base - 1 과 (base - 1) 의 약수들이 그 답이란 것을 쉽게 찾을 수 있다.

 

다음은 JAVA 코드이다.

벡터와 배열을 다루는 법을 알아야 코드를 작성할 수 있으니 벡터와 배열을 다시한번 공부하는 계기가 될 것이다.

 

    public static int[] answer(int base){
        Vector<Integer> v = new Vector<Integer>(); // 정답을 위한 벡터 선언
       
        for(int i = 2; i < base; i++){
            if((base - 1) % i == 0){ // 파라미터로 주어진 base 보다 1 작은 것과 그 약수들이면
                v.add(i); // 정답에 포함 시킨다
            }
        }
        int[] ans = new int[v.size()]; // 벡터에 담긴 정답들을 옮기기 위한 배열 선언
        for(int i = 0; i < v.size(); i++){
            ans[i] = v.get(i); // 벡터의 원소 옮기기
        }
       
        return ans;  
    }