Lv.2 / N개의 최소공배수

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

---

 

코드

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

using namespace std;

int getGCD(int n1, int n2) {
    int tmp;
    
    while(true) {
        if((n1 % n2) == 0) return n2;
        
        tmp = n1;
        n1 = n2;
        n2 = tmp % n2;        
    }    
}

int solution(vector<int> arr) {
    int answer = 0;
    
    answer = arr[0] * arr[1] / getGCD(max(arr[0], arr[1]), min(arr[0], arr[1]));
    
    for(int i=2; i<arr.size(); i++) {
        answer = answer * arr[i] / getGCD(max(answer, arr[i]), min(answer, arr[i]));
    }
    
    return answer; 
}

---

 

풀이

두 수의 최소공배수는 두 수의 곱 / 최대공약수 이다.

최대공약수를 구할 때에는 유클리드 호제법을 이용하였다.

 

처음 두 수의 최소공배수를 answer 에 저장한 뒤에 다음 수부터 answer 와 배열의 수의 최소공배수를 단계적으로 구했다.