C++로 LCM이 최대가 되는 N 이하의 세 정수 찾는 방법

이 튜토리얼에서는 주어진 정수 N보다 작거나 같은 세 정수를 찾아, 그 세 수의 최소공배수(LCM)가 가능한 한 최대가 되도록 만드는 프로그램을 살펴봅니다.

정수 하나가 입력으로 주어지면, 그 값 이하의 범위에서 세 정수를 골라 세 수의 LCM이 최대가 되는 조합을 출력하는 것이 목표입니다.

접근 방법

세 수의 곱이 클수록 LCM도 커지는 경향이 있으므로, 직관적으로는 N에 가장 가까운 연속된 세 수 N, N-1, N-2가 답일 것 같습니다. 하지만 N이 짝수라면 N과 N-2가 공약수 2를 공유하여 LCM이 손실되므로, 경우를 나누어 생각해야 합니다.

1. N이 홀수인 경우

N, N-1, N-2는 서로 인접하거나 차이가 2인 홀수·짝수 조합이라 세 수 모두 서로소(최대공약수 1)입니다. 따라서 LCM은 곧 N × (N-1) × (N-2)가 되며, 이보다 큰 값을 만들 수 없으므로 이 조합이 정답입니다.

2. N이 짝수이고 N과 N-3이 서로소인 경우

N이 짝수면 N과 N-2는 둘 다 짝수이므로 함께 사용할 수 없습니다. 대신 gcd(N, N-3) = 1이라면 N, N-1, N-3을 선택합니다. 예를 들어 N = 10일 때 10, 9, 7의 LCM은 630으로, 10, 9, 8의 LCM(360)보다 큽니다.

3. 위 두 경우에 해당하지 않는 경우

N이 짝수이면서 동시에 3의 배수라면(N = 6, 12, 18 등) gcd(N, N-3)이 1이 아니므로, 안전하게 N-1, N-2, N-3을 선택합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

// 주어진 값 이하에서 LCM이 최대가 되는 세 정수를 찾는 함수
void findMaximumLCM(int n) {
    if (n % 2 != 0) {
        // N이 홀수인 경우: N, N-1, N-2는 서로소
        cout << n << " " << (n - 1) << " " << (n - 2);
    }
    else if (__gcd(n, (n - 3)) == 1) {
        // N이 짝수이고 N과 N-3이 서로소인 경우
        cout << n << " " << (n - 1) << " " << (n - 3);
    }
    else {
        // 그 외의 경우: N-1, N-2, N-3 선택
        cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
    }
}

int main() {
    int number = 34;
    findMaximumLCM(number);
    return 0;
}

실행 결과

34 33 31

동작 원리와 시간 복잡도

예제의 N = 34는 짝수이고, gcd(34, 31) = 1이므로 두 번째 분기에 걸쳐 34, 33, 31이 출력됩니다. 실제로 LCM(34, 33, 31) = 34 × 33 × 31 = 34,782로, 34 이하의 어떤 세 정수 조합보다도 큽니다.

이 알고리즘은 단순한 홀짝 판별과 한 번의 GCD 계산만으로 답을 구하므로 시간 복잡도는 O(log N)으로 매우 효율적입니다. 참고로 __gcd 함수는 GCC 전용 내장 함수이므로, 코드 이식성을 고려한다면 C++17의 <numeric> 헤더에 있는 std::gcd를 사용하는 것이 좋습니다.