[프로그래머스]Lv 2. N개의 최소공배수

본 페이지는 C++ 독학을 위해 작성한 포스트입니다 풀이과정도 포함되어있지만 문법공부에 대한 비중이 있습니다.
(+  Java언어 내용도 포함되어있을 수 있습니다. )

 

 

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

프로그래머스

 

1.문제설명

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

 

2. 문제해결 접근

• 유클리드 호제법을 이용하면 손 쉽게 풀이할 수 있다.

최대공약수와 최소공배수는 유클리드 호제법이라는 개념으로 정립되어있다.

 

 

https://imkh.dev/algorithm-gcd-lcm/

최소공배수와 최대공약수 알고리즘 (유클리드 호제법) | imkh.dev

 

3.C++ 답안

#include <string>
#include <vector>
#include <algorithm>
using namespace std;
// 최대 공약수 구하는 gcd
int gcd(int x, int y) { return x % y == 0 ? y : gcd(y, x % y); }
// 최소 공배수 구하는 lcm 
int lcm(int x, int y) { return x * y / gcd(x, y); }

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

점점 혼자힘으로 풀어가는게 힘들어지는건 기분탓이겠지...