[009] N개의 최소공배수

 

 

---

 

최소공배수와 최대공약수는 계속해서 나오는 거라 그냥 외워버렸다 (...)

최대공약수를 구하는 것은 결국 계속해서 약분하여 제일 작은 수가 나올 때까지 반복하는 것이기 때문에

    public static int gcd(int a, int b){
        if (a % b == 0){
            return b;
        }
        return gcd(b, a % b);
    }

 

와 같은 형태로 구한다.

a랑 b를 나누고 이것의 나머지가 0이 되면 바로 b를 리턴해버리고, 그게 아니라면 다시 b와, a를 b와 나눈 나머지를 리턴하는 형태 

 

최소공배수는 최대공약수 * a * b의 형태이기 때문에

 

public static int lcm(int a, int b){
        return a * b / gcd(a, b);
    }

 

의 형태로 나타내면 된다.

 

    public int t03(int[] arr) {
        int answer = arr[0];

        for(int i = 1; i < arr.length; i++){
            answer = lcm(answer, arr[i]);
        }

        return answer;
    }


    public static int gcd(int a, int b){
        if (a % b == 0){
            return b;
        }
        return gcd(b, a % b);
    }

    public static int lcm(int a, int b){
        return a * b / gcd(a, b);
    }

 

이 문제의 경우 배열의 최대공배수를 구하는 것이기 때문에 배열을 순회하면서 최대공배수를 계속해서 구해주면 됨!