최소 공배수의 합

양의 정수의 배열 arr이 주어질 때 모든 원소들이 둘 씩 짝지어 생기는 최소공배수를 합한 값을 리턴하는 solution 함수를 작성해주세요.

 

🚩 [제한사항]

- arr 내 원소들은 중복되지 않습니다.

- arr 배열의 길이는 최소 3입니다.

- 입출력 예 : [ 1 , 2 , 3 ] → ( {1 | 2} → 2 + { 1 | 3 } → 3 + { 2 | 3 } → 6 ) = 11

 

import java.util.Arrays;

class Solution {
    public int solution(int[] arr) {
        int answer = 0;
        int n = arr.length;

        //배열의 최소공배수
        int lcm = arr[0];
        for (int i = 1; i < n; i++) {
            lcm = getLCM(lcm, arr[i]);
        }

        //최소공배수의 합
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n; j++) {
                int temp = getLCM(arr[i], arr[j]);
                answer += temp;
            }
        }
        answer *= lcm;
        return answer;
    }

    // 최대공약수
    private int getGCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        return getGCD(b, a % b);
    }

    // 최소공배수
    private int getLCM(int a, int b) {
        return (a * b) / getGCD(a, b);
    }
}

유클리드 호재법을 이용해서 해결함.. 

 

전에 유클리드 호재법관련 레퍼런스들을 많이 보고 한번해봐야겠다 라고 생각 했는데 겸사겸사 공부하면서 풀었다.

 

 

문제풀이

 

 

최소 공배수 : (a ✕  b) / (최대 공약수) 의 식을 이용하기로 함.

** arr 배열의 길이는 3이상.. !

그럼 A,B의 최소공배수를 구하고 ,그 최소공배수와 C의 최소공배수를 구하고 합하면 해결. 

 

 

 

Reference

https://programmer-chocho.tistory.com/9#--%--%EC%--%AB%EA%B-%--%--%EC%--%AC%EB%-F%AC%EA%B-%-C%EC%-D%BC%--%EB%--%-C%C-%A-%---%EB%A-%A-%EA%B-%-C%EB%B-%--%EC%--%--%--%EB%B-%B-%EC%--%B--

 

https://seeminglyjs.tistory.com/89