[C++][프로그래머스]연습문제_N개의 최소공배수

문제 번호

https://programmers.co.kr/learn/courses/30/lessons/12953?language=cpp 

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

 

 

 

알고리즘 분류

 수학

 

문제 풀이

 예전에 풀어보았던 문제랑 비슷하다. 이 문제를 해결하기 위해서는 최대 공배수를 구하는 유클리드 호제법(GCD)을 알 필요가 있다. 간단하게 GCD는 2개의 자연수 또는 정식의 최대 공약수를 구하는 알고리즘이다.

 

GCD : 

int gcd(int a, int b){
    if(a<b){
        int temp=a;
        a = b;
        b = temp;
    }
    
    int n = a%b;
    while(b!=0){
        n = a%b;    
        a = b;
        b = n;
    }
    
    return a;
}

 두 수 a,b 가 주어지면 a를 더 큰 수라고 할 때 다음과 같은 과정을 통하여 a와 b의 최대 공약수를 구할 수 있다. 이후 a, b의 최소공배수는 'a*b/최대공약수'를 통하여 얻을 수 있다.

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

 

전체 코드 

#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int gcd(int a, int b){
    if(a<b){
        int temp=a;
        a = b;
        b = temp;
    }
    
    int n = a%b;
    while(b!=0){
        n = a%b;    
        a = b;
        b = n;
    }
    
    return a;
}

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

int solution(vector<int> arr) {
    int answer = 1;
    
    for(int i=0; i<arr.size();i++){
         answer = lcs(answer, arr[i]);
    }
    
    return answer;
}

 

특이사항

 GCD는 풀어봤던 문제지만 자주 사용하지 않아서 정확하게 기억나지 않았다. 꾸준하게 복습해서 잊어버리지 않도록 주의 해야겠다. 매우 쉬운 문제였으나 생각보다 오래 걸렸다.