C++로 두 피보나치 수의 최소공배수(LCM) 구하는 프로그램

이 문제에서는 두 개의 정수 N과 M이 주어집니다. 우리의 목표는 C++로 두 피보나치 수의 최소공배수(LCM)를 구하는 프로그램을 작성하는 것입니다.

문제 설명

N번째 피보나치 수와 M번째 피보나치 수를 각각 구한 뒤, 두 수의 최소공배수를 계산하여 그 결과를 반환합니다.

피보나치 수열

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...

예시로 이해하기

입력: N = 4, M = 9

출력: 42

풀이 과정

4번째 피보나치 수는 2입니다.

9번째 피보나치 수는 21입니다.

따라서 두 수의 최소공배수인 42가 결과가 됩니다.

해결 접근 방법

이 문제는 다음 세 단계로 나누어 해결할 수 있습니다.

1. N번째 피보나치 수를 계산합니다.
2. M번째 피보나치 수를 계산합니다.
3. 두 피보나치 수의 최소공배수를 구하여 반환합니다.

최소공배수는 일반적으로 GCD(최대공약수)를 활용한 공식 LCM(a, b) = (a × b) / GCD(a, b)로 효율적으로 구할 수 있습니다. 아래 예제에서는 두 수 중 큰 값부터 시작해 두 수의 공통 배수를 찾을 때까지 값을 증가시키는 반복 방식으로 LCM을 구했습니다.

예제 코드

#include <iostream>
using namespace std;

long int fibo(int N){
    long int a = 0, b = 1, c;
    for(int i = 2; i < N; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

int findLCM(int a, int b){
    int max, step, lcm;
    lcm = 0;
    if(a > b)
        max = step = a;
    else
        max = step = b;
    while(1) {
        if(max % a == 0 && max % b == 0) {
            lcm = max;
            break;
        }
        max += step;
    }
    return lcm;
}

int CalcFiboLCM(int N, int M) {
    int fiboN = fibo(N);
    int fiboM = fibo(M);
    return findLCM(fiboN, fiboM);
}

int main() {
    int N = 5, M = 14;
    cout << "두 피보나치 수의 LCM은 " << CalcFiboLCM(N, M);
    return 0;
}

출력 결과

두 피보나치 수의 LCM은 699

위 실행 결과에서 N = 5일 때 5번째 피보나치 수는 3, M = 14일 때 14번째 피보나치 수는 233이며, 두 수의 최소공배수는 699입니다.

참고: 위의 fibo 함수는 N이 3 미만일 경우 초기화되지 않은 변수를 반환할 수 있으므로, 실제 프로젝트에서는 N이 1 또는 2일 때 각각 0과 1을 반환하도록 예외 처리를 추가하는 것이 안전합니다. 또한 입력 값이 커질 경우 오버플로우를 방지하기 위해 long long 자료형이나 모듈러 연산을 고려하는 것이 좋습니다.