[프로그래머스] level2. N개의 최소공배수 (자바 JAVA)

[ 문제 ]  [프로그래머스] level2. N개의 최소공배수 (자바 JAVA)

 

문제 링크 : https://programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

---

# 접근 방법 및 풀이 

 

• 두 수의 최대공약수와 최소공배수 구하는 법은 익히 공식을 알아 쉬웠다.
• 여기서 N개의 최소공배수를 구하기 위해선 다음과 같은 법칙(?)을 알아야한다.
• 3가지 수 A, B, C 가 있을때 두 수 A와 B의 최소공배수가 k라면, k와 C의 최소공배수는 A, B, C의 최소공배수다.
• 최대공약수도 위의 내용을 만족한다. 
• 따라서 N개의 최소 공배수를 구하기 위해선 두 수의 최소공배수를 구한 후, 구한 최소공배수와 다음 숫자와의 최소공배수를 쭉 구해주면된다.
• 난 이걸 떠올리지 못해서 인터넷 찾아봤다,, 근데 알고보니 정올문제에서 풀어봤던거다 ^^... 또 틀리지말자.
• 먼저 최소공배수 LCM은 두 수 N*M / GCD(최대공약수) 라는 공식을 써서, 최대공약수를 구하고 최소공배수를 구해도 되지만, 최소공배수 구할때 for문 써서 구했다.
• 예를들어, 4, 8이 있을때, 두수를 곱한 i = 32부터 ~1까지 해당 i가 4와 8로 둘다 나누어 떨어질때까지 해서 최소공배수값을 갱신하는 형태로 구해줬다.

# 주의할 점 

 

• 수학공부 하자..

 

JAVA 코드

import java.util.*;
class Solution {
    public int solution(int[] arr) {
        if(arr.length == 1){
            return arr[0];
        }
        int a = arr[0];
        int gcd = 0;
        for(int i = 1; i < arr.length; i++){
            int b = arr[i];
            for(int j = a*b; j > 0; j--){
                if((j%a == 0) && (j%b == 0))
                    gcd = j;
            }
            a = gcd;
        }
        return gcd;
    }
}

 

 

 

REVIEW