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

문제

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

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

 

계획 세우기

예제에서 1 5 7 9 2 6가 주어지는데, 재귀 함수를 이용해서 이 수들의 최소공배수를 구해야 한다.

단순하게 생각하면 LCM(1, LCM(5, LCM(7, LCM(9, LCM(2, 6)))))

이렇게 두 수 + 그 다음 수의 최소공배수를 구하도록 만들면 된다.

LCM(LCM(n, m), m+1) 이런 식으로 호출

 

LCM함수에 뭘 넣을지도 고민이다. LCM을 구하는 법은 LCM(a, b)라고 했을 때 a*b / GCD(a, b)이다.

LCM(LCM(n, m), m+1)을 한다고 치면

LCM(LCM(n, m), m+1) = LCM(n*m/GCD(n, m) , m+1) = (n*m/GCD(n, m) * m+1) / GCD(n*m/GCD(n, m), m+1)

위와 같이 되어야 한다....

 

LCM(n, m)은 return LCM(n*m/GCD(n, m) , m+1) ←이렇게 해주는 게 기본 형태일 것 같다(맞나...?)

n, m에는 1, 5, 7, 9, 2, 6이 차례대로 들어가야 하는데, 인덱스로 넘겨줄지 값으로 넘겨줄지도 고민이다...

 

 

 LCM(1, LCM(5, LCM(7, LCM(9, LCM(2, 6))))) 혹은LCM(LCM( LCM(LCM(1, 5), 7), 9), 2), 6) 이런식으로 호출되도록 만들어야 한다는 것까지는 생각했다.

문제는 LCM(1, 5)만 생각하면 idx 0, 1이 들어간 것인데, LCM(LCM(1, 5), 7)이 되면 LCM(1, 5)는 인덱스가 아니기 때문에 이상한 값이 나올 것 같다...

결국 토론 게시판에 질문을 남겨서 힌트를 얻었다.

 

n 개의 수 a[0], ... , a[n-1]이 주어졌을 때, 이 수들의 합을 구하는 코드를 먼저 재귀함수로 작성했을 때,  덧셈 파트를 lcm으로 바꾸면 원하는 코드를 짤 수 있다는 것이다.

 

 

풀이

#include <iostream>

using namespace std;

int *arr;
int n;

int GCD(int n, int m){
    if(n*m==0) return n+m;
    return GCD(m, n%m);
}

int LCM(int a, int b){
    return a*b/GCD(a, b);
}

// n 개의 수 a[0], ... , a[n-1]이 주어졌을 때, 이 수들의 합을 구하는 코드
//int Sum (int idx){
//    if(idx==0) return arr[idx];
//    return Sum(idx-1)+arr[idx];
//}

// n개의 수가 주어졌을 때 최소공배수 구하기
int LCMAll(int idx){
    if(idx==0) return arr[idx];
    return LCM(LCMAll(idx-1), arr[idx]);
}
int main() {
    //input
    cin >>n;
    arr = new int[n];
    for (int i=0;i<n;i++){
        cin >> arr[i];
    }

    //lcm[0]=arr[0];
    //lcm[1]=arr[1];
    //for(int i=2;i<n;i++){
    //    int a = lcm[i-1];
    //    int b = arr[i];
    //    lcm[i]=a*b/GCD(a, b);
    //    //cout << "i: "<< i << " "<< lcm[i] <<'\n';
    //}
    cout << LCMAll(n-1);
    return 0;
}