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

문제

N개의 최소공배수 : 문제 링크

문제 분석

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

• 제한 사항

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

• 유클리드 호제법에 따라 두 정수의 최대공약수를 구하는 함수 gcd를 초기화. if문을 통해 a를 b로 나눈 나머지가 0이라면 b를 return하고, 아니라면 else문을 통해 (b, a % b) 형태로 재귀. 두 정수의 최소공배수를 구하는 함수 lcm을 초기화. 최소공배수는 두 정수의 곱을 최대공약수로 나눠서 구할수 있으므로, 앞서 만든 함수 gcd를 활용.
• solution 함수에서는 if문을 사용하여 arr의 길이가 1이라면 숫자가 하나이므로 그 수를 return. 이외의 경우는 else문을 사용하여 정수형 변수 lcm_s에 arr의 첫번째, 두번째 원소의 최소공배수를 저장. for loop를 통해 arr의 2번째부터 마지막 원소까지 순환하면서, lcm_s와 현재 인덱스 원소의 최소공배수를 구하여 lcm_s에 저장하는것을 반복. loop 탈출 후, 최종적으로 저장된 lcm_s를 return

유클리드 호제법

• a, b가 정수이고 a >= b라고하고, a를 b로 나눈 나머지를 r이라고 한다. 이때 a와 b의 최대공약수를 (a, b)라고 하면 (a, b) = (b, r)이 성립한다.

풀이

#include <vector>

using namespace std;

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

int lcm(int a, int b) {
    return a * b / gcd(a, b);
}

int solution(vector<int> arr) {
    if(arr.size() == 1) return arr[0];
    else {
        int lcm_s = lcm(arr[0], arr[1]);
        for(int i = 2; i < arr.size(); ++i) {
            lcm_s = lcm(lcm_s, arr[i]);
        }
        return lcm_s;
    }
}