프로그래머스, N개의 최소공배수 : C++ [CPP]

 

이것도 그냥 수학이다.

 

 

유클리드 호제법을 이용하면 된다.

간략하게 말해서

G(A,B) = G(B, A%B)와 같다.

 

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

 

---

 

#맞은 풀이

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

using namespace std;

//최소 공배수를 구하기 위해 최대공약수를 알아보자
//유클리드 호제법 사용

int max(int a, int b){
    //a가 b보다 크다는 가정
    if(a<b){
        int temp = a;
        a = b;
        b = temp;
    }
    
    if(a%b == 0){
        //b로 나눠지면 b가 최대 공약수
        return b;
    }else{
        return max(b, a%b);
    }
}

int min(int a, int b){
    int x = (a*b) / max(a,b); //Ga * Gb / G는 Gab

    return x;
}




int solution(vector<int> arr) {
    int answer = 0;
    int size = arr.size();
    int def = 1;
    //size만큼 연산-> n개의 원소면 n번 연산
    while(size){
        def = min(def,arr[size-1]); //현재까지 계산된 최소 공배수와 다음 원소와의 최소공배수
        
        size--;
    }
    // 끝나면 def가 모든 수에 대한 최소공배수임.
    answer = def;
    return answer;
}

 

간단히 써놨다.

알기 쉽기도 하다.

너무 좋다.

오류 없이 한 번에 풀어서 기분 좋다.