[Programmers_C++]#Level2_N개의 최소 공배수, 유클리드 호제법, 최대 공약수, 최소 공배수

 

#1. 문제

 

 

---

 

#2. 풀이

 

1. 유클리드 호제법

[BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법

 

Details

 

'유클리드 호제법'은 두 수 a와 b의 최대 공약수를 구하는 알고리즘입니다. 이 알고리즘은 두 정수 a와 b의 최대 공약수가 a와 b를 나눈 나머지 값을 이용하여 계속 나누는 과정을 반복하다가, 나머지가 0이 되어 나누어 떨어지는 수가 생기면 그 수가 두 수의 최대 공약수가 되는 점을 활용합니다.

 

2. 최대 공약수, gcd

int gcd(int a, int b)
{
	int c = a%b;
    while(c != 0)
    {
    	a = b;
        b = c;
        c = a%b;
    }
    return b; 
}

 

3. 최소 공배수, lcm

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

 

4. 세 정수 A, B, 그리고 C의 최소 공배수는 lcm(lcm(a, b), c)와 같다!

1. vector 컨테이너의 0번째 항목과 1번째 항목의 lcm 값을 먼저 계산합니다.
2. 이후, vector 컨테이너의 2 번째 항목부터 차례대로 순회하며 lcm 값을 업데이트 합니다.

 

---

 

#3. 코드

 

#include <string>
#include <vector>

using namespace std;

/*

    a, b, 그리고 c의 최소 공배수는 lcm(lcm(a,b), c) 와 같습니다.

*/

int gcd(int a, int b)
{
    int c = a % b;
    while (c != 0)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

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

int solution(vector<int> arr)
{
    int answer = 0;

    if ((int)arr.size() < 2)
        return arr[0];

    answer = lcm(arr[0], arr[1]);

    for (int i = 2; i < arr.size(); ++i)
    {
        answer = lcm(answer, arr[i]);
    }

    return answer;
}

 

---