[프로그래머스 lv2] N개의 최소공배수 (최대공약수, 최소공배수) [C++]

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

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

---

처음엔 배열의 최댓값부터 1씩 증가하면서, 모든 원소와 최초로 나눠 떨어지는 수를 찾았다.

맞았지만, 데이터의 크기가 커지면 시간 초과가 날 수 있는 풀이였다.

 

다른 분들의 풀이를 보니, 최대공약수와 최소공배수를 구해서 풀었다.

 

a와 b의 최소공배수를 구하는 것은 a와 b의 곱을 최대공약수로 나눈 것이기 때문에 배열의 값들을 짝지어서 곱하고 그 두 수의 최대공약수로 나누는 풀이였다.

 

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

using namespace std;

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

int lcm(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 = lcm(answer, arr[i]);
    }
    return answer;
}

깔끔한 풀이다.