프로그래머스 - N개의 최소공배수

 이 문제는 유클리드 호제법을 이용한 문제이다. 나는 이 문제를 풀 때 처음에 주어진 배열 안 모든 숫자에 대한 최대공약수와 최소공배수를 구하려고 했다. 하지만 이렇게 풀면 정답이 나오지 않는다. 정확한 방법은 두 수씩 짝을 지어서 그 수에 대한 최소공배수를 얻고, 그 다음 수와 이전 결과로 나온 수를 짝짓는 식으로 해야 올바른 답이 나온다. 개념에 오류가 있어 헤맸던 문제였다.

 

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

using namespace std;

int gcd(int a, int b) {
    if (a < b) {
        swap(a, b);
    }
    
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int solution(vector<int> arr) {
    unsigned long long answer = 0;
    
    // base case
    if (arr.size() == 1) {
        return arr[0];
    }
    
    answer = arr[0];
    for (int i = 1; i < arr.size(); i++) {
        int temp = gcd(answer, arr[i]);
        int lcm = answer * arr[i] / temp;
        answer = lcm;
    }
    
    
    return answer;
}