[코드트리 조별과제] 재귀함수를 이용한 최소공배수 C++ 풀이

---

알고리즘 분류

• 수학

---

문제 설명

n개의 수가 주어졌을 때 이 수들의 최소공배수를 구하는 프로그램을 작성해 보세요. 단, 재귀함수를 이용하여 문제를 해결해 주세요.

---

입력 설명

첫 번째 줄에 정수 n이 주어집니다.

두 번째 줄에 n개의 수가 공백을 사이에 두고 주어집니다.

• 1 ≤ n ≤ 10
• 1 ≤ 원소의 범위 ≤ 10

---

출력 설명

첫 번째 줄에 n개의 수들의 최소공배수를 출력합니다.

---

예제 입력

6
1 5 7 9 2 6

---

예제 출력

630

---

아이디어

최대공약수와 최소공배수를 구하는 함수를 만들고 모든 입력받은 값을 벡터에 저장하여 소모하면서 연속적으로 최소공배수를 구한다.

---

알고리즘

최대공약수는 유클리드 호제법을 이용하면 간단하게 구할 수 있다.

유클리드 호제법에 따르면 a와 b의 최대 공약수는 b와 a% b의 최대 공약수와 같다.

따라서 만약 b가 0이라면 a가 최대 공약수이고 b가 0이 아니라면 b와 a% b의 최대 공약수를 구하는 것을 재귀적으로 구현한다.

최소공배수는 a와 b의 곱을 아까 구한 a와 b의 최대공약수를 나누어주면 된다. 즉, a * b / gcd(a, b)이다.

입력받은 모든 값을 벡터에 넣고 백터의 크기가 0이 될 때까지 하나씩 빼면서 재귀적으로 최소공배수를 구한다.

---

코드

#include <iostream>
#include <vector>
using namespace std;
int gcd(int a, int b)
{
    if(b==0) return a;
    return gcd(b,a%b);
}
int lcm(int a, int b)
{
    return (a*b/gcd(a,b));
}
int main() {
    int n,c,temp;
    vector<int> vec;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>temp;
        vec.push_back(temp);
    }
    temp = 1;
    while(vec.size() != 0)
    {
        temp = lcm(temp, vec.back());
        vec.pop_back();
    }
    cout<<temp;
    return 0;
}

---

후기

문제 링크 -> https://www.codetree.ai/missions/5/problems/least-common-multiple-using-recursive-function?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

그냥 a와 b의 최대공약수, 최소공배수를 구하는 문제는 많이 풀어봤지만 재귀적으로 여러 값을 동시에 구하는 것은 처음 풀어봤다. 문제를 처음 풀 때는 이를 재귀적으로 함수 내에서 어떻게 구현해야 할지 오래 고민했지만 결론적으로 함수는 본연의 역할만 충실하게 간단하게 구현하고 그 밖에서 재귀를 사용하는 편이 수월하다고 생각하여 그렇게 구현했다.

최대공약수와 최소공배수 구하는 문제는 간단하면서도 자주 나오는 것 같다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!