[프로그래머스] 12953. N개의 최소공배수

문제 링크

[프로그래머스] 12953. N개의 최소공배수

풀이 과정

세 수 A, B, C가 있을 때, A와 B의 최소 공배수를 D라고 하면,

A, B, C의 최소 공배수는 D, C의 최소 공배수 와 같습니다.

위의 사실을 배열의 각 요소에 적용시켜, 최소 공배수를 누적해나가는 방식으로 문제를 해결했습니다.

유클리드 호제법을 사용해 최대 공약수를 구했으며, 구한 최대 공약수를 이용해 최소 공배수를 구했습니다.

코드

public class Main {
    public static int solution(int[] arr) {
        int val = arr[0];

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

        return val;
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int r = a % b;
            a = b;
            b = r;
        }

        return a;
    }

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

    public static void main(String[] args) {
        int[] arr = {2, 6, 8, 14};
//        int[] arr = {1, 2, 3};
        System.out.println(solution(arr));
    }
}