[TIP] GCD, LCM

·2021년 9월 22일
0

Coding Test

목록 보기
2/3

유클리드호제법

최대공약수 GCD

GCD( A , B ) = GCD( B , A%B )
if      A%B == 0   ->   GCD = B
else   GCD( B , A%B )

최소공배수 LCM

LCM = A * B / GCD



예제

// N개의 최소공배수 구하기
#include <string>
#include <vector>

using namespace std;

// 최대공약수 구하는 함수
int gcdf(int a, int b){
    if(a%b == 0) return b;
    return gcdf(b, a%b);
}

// 최소공배수 구하는 함수
int lcmf(int a, int b){
    return a * b / gcdf(a, b);
}


int solution(vector<int> arr) {
    int arrlen = arr.size(); //vector의 크기
    
    // vector의 뒤에서부터 하나씩
    for(int i = arrlen - 1; i > 0; i-- ){
        // vector 의 제일 끝값 두개의 최소공배수를 구함
        int lcm = lcmf(arr[i], arr[i-1]);
        
        // 두 값을 빼고
        arr.pop_back();
        arr.pop_back();
        // 구한 최소공배수 값을 넣는다.
        arr.push_back(lcm);
    }
        
    return arr[0];
}
profile
나그네 개발자

0개의 댓글