[c++]N개의 최소공배수

출처: 프로그래머스

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

입출력 예

arr	result
[2,6,8,14]	168
[1,2,3]	6

 

문제 풀이

#include <string>
#include <vector>

using namespace std;

int gcd(int a, int b){
    int maxgcd = 1;
    int range = min(a,b); //둘중에 최소값을 범위로 지정
    
    //값을 두 숫자중 최소값으로 줄여가면서 최대공약수 찾기
    for(int i = range; i > 0; i--){
        if(a % i == 0 && b % i == 0 ){
            maxgcd = i;
            break;
        }
    }
    return maxgcd;
}

int lcm(int a, int b) {
	//최소 공배수는 최대공약수 사이의 상관관계를 통해 구할 수 있음
    return (a / gcd(a, b)) * b;
}


int solution(vector<int> arr) {
    int answer = arr[0];
    for (int i = 1; i < arr.size(); i++) {
    	//두 수의 공배수를 구한후 배열의 값을 순서대로 넣어 최소공배수를 구할 수 있음
        answer = lcm(answer, arr[i]);
    }
    return answer;
}

 

최소공배수와 최대공약수의 관계를 이해해야 하는 문제이다. 또한 최소공배수는 결합법칙을 따르기에 두 수에서 최소공배수를 구한 후 다른 수와의 공배수를 구하여도 된다. 수학적인 이해가 있어야 풀이가 쉬워지는 문제였다.