# 프로그래머스 : N개의 최소공배수 (Level 3)

[문제]

 두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. nlcm 함수를 통해 n개의 숫자가 입력되었을 때, 최소공배수를 반환해 주세요. 예를들어 [2,6,8,14] 가 입력된다면 168을 반환해 주면 됩니다.

[풀이]

우선 최대공약수, 최소공배수의 개념을 명확하게 알아야 할 것 같았다.
손으로 풀때랑, 실제 코드 상으로(수학적 공식으로) 적는 것은 차이가 있었는데,

• 최대 공약수
• 두 수의 공약수 중 가장 큰 수 (이건 누구나 알고 있는 개념)
• 나머지가 0이 나올 때 까지 제수를 나머지로 다시 나누는 방법을 반복 (몰랐다!)

최대 공약수를 구하는 2번째 방법을 식으로 정리해보면,

1. x % y != 0 이면, y % (x % y)
2. y % (x % y) != 0 이면, (x % y) % {y % (x % y)}
3. 2번의 동작을 m % n == 0일 때 까지 반복

이를 코드로 표현하면 다음과 같다.

long long gcd (long long x, long long y) {

    if(x%y == 0)    return y;

    else            return gcd(y, x%y);

}

그렇다면 최소 공배수는 어떻게 표현할 수 있을까?

• 최소 공배수
• 두 수의 공배수 중 가장 작은 수 (이것 또한 누구나 알고 있는 개념)
• 두 수의 곲을 최대 공약수로 나눈 수 (몰랐다!!)

최소 공배수를 구하는 2번째 방법을 코드로 표현하면 다음과 같다.

long long lcm (long long x, long long y) {

    return (x * y) / gcd(x,y);

}

그러므로 최종 식을 표현하면,

long long nlcm(vector<int> num)

{

    long long answer = 0;

    sort(num.begin(), num.end(), greater<int>());

    for(int i=0; i<num.size(); i++) {

        if(i==0) answer = num[i];

        else {

            if(answer > num[i]) answer = lcm(answer, num[i]);

            else answer = lcm(num[i], answer);

        }

    }

    return answer;

}

여기서 sort 함수는 자동으로 배열 내의 원소를 정렬해주는 API이다.

전달 값 중에서 greater<int>는 배열 내 원소를 내림 차순으로 정렬하겠다는 의미이다.

배열을 처음부터 돌아가면서 큰 수부터 차례대로 최소 공배수를 확인하는 방식이다.