프로그래머스 N개의 최소공배수 C언어

1. 최대공약수 구하는 방법 

큰 수 : a , 작은 수 : b

a가 b로 나누어 떨어진다면 최대 공약수는 b

그렇지 않다면 a와 b의 최대 공약수는 b 와 (a를 b로 나눴을 때의 나머지)의 최대 공약수와 같다.

큰 수 b , 작은 수 R로 진행하여 두 수가 나누어 떨어질 때까지 while문을 반복한다.

 

2. 최소 공배수 구하는 방법

1에서 구한 최대공약수 GCD * ( a / GCD ) * ( b / GCD ) 값이 된다.

 

3. 최소 공배수 값을 저장할 lcm_arr를 선언하고 lcm_arr[0] = 1 설정해준다.

아래와 같이 입력 배열 arr 을 차례로 비교하면서 최소 공배수 값을 갱신한다. 

arr[0] 2 , lcm_arr[0] 1 => lcm_arr[1] 2

arr[1] 6 , lcm_arr[1] 2 => lcm_arr[2] 6

 

i	0	1	2	3	4
arr[i]	2	6	8	14
lcm_arr[i]	1	2	6	24	168

 

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
int get_GCD(int a, int b){
    int bigger, smaller, R;
    bigger = a; smaller = b;
    while(1){
        if(bigger < smaller) {
            bigger = b;
            smaller = a;
        }
        R = bigger%smaller;
        if(R==0){
            return smaller;
        }
        else{
            bigger = smaller;
            smaller = R;
        }
    }
}
 
int get_LCM(int a, int b){
    int GCD = get_GCD(a, b);
    int a_ = a / GCD;
    int b_ = b / GCD;
    
    return (GCD * a_ * b_);
}
 
 
// arr_len은 배열 arr의 길이입니다.
int solution(int arr[], size_t arr_len) {
    int answer = 0;
    int lcm_arr[16];
    lcm_arr[0] = 1;
    for(int i = 0; i < arr_len; i++){
        lcm_arr[i+1] = get_LCM(lcm_arr[i], arr[i]);
    }
    answer = lcm_arr[arr_len];
    return answer;
}