C언어 ] 프로그래머스 Lv. 2 - N개의 최소공배수

문제 설명

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

 

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

 

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

 

 

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

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

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

// arr_len은 배열 arr의 길이입니다.
int solution(int arr[], size_t arr_len) {
    int answer = 0;
    
    answer = arr[0];
    
    for(int i = 1; i< arr_len; i++)
    {
        answer = lcm(answer, arr[i]);
    }
    
    return answer;
}

 

최소공약수(gcd)와 최소공배수(lcm)을 구하는 코드는 이미 잘 알려져 있다.

유클리드 호제법을 사용한다.

gcd(a, b) = gcd(b, a%b)

a%b를 c라고 했을때 (a, b)의 최대공약수는 (b, c)의 최소공약수와 같다. c가 0이 될때까지 반복하면 b가 최대공약수가 된다.

a * b = gcd(a, b) * lcm(a,b)

 

이후 배열의 끝까지 순회하며 인접하는 수와 최소공배수를 구해나가면 된다.