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

이 튜토리얼에서는 LCM(최소공배수) 개념을 활용한 프로그램을 작성해 보겠습니다. 목표는 주어진 수 N보다 작거나 같은 세 정수 중에서 LCM이 최대가 되는 조합을 찾는 것입니다.

간단한 예시로 문제를 이해한 뒤, LCM의 개념과 구현 방법을 차례대로 살펴보겠습니다.

LCM(최소공배수)이란?

LCM(Least Common Multiple, 최소공배수)은 두 수가 공통으로 가지는 배수 중 가장 작은 수를 의미합니다. 두 양의 정수 a와 b의 LCM은 a와 b 모두로 나누어 떨어지는 가장 작은 양의 정수입니다.

특히 두 수가 서로소, 즉 1 외의 공약수를 갖지 않는다면 LCM은 단순히 두 수의 곱이 됩니다. 예를 들어 4와 5는 서로소이므로 LCM은 4 × 5 = 20입니다.

두 수의 LCM 구하기

먼저 두 양의 정수의 LCM을 구하는 간단한 프로그램부터 작성해 보겠습니다.

#include <iostream>
using namespace std;

int main() {
    int a = 4, b = 5;
    int maximum = max(a, b);
    while (true) {
        if (maximum % a == 0 && maximum % b == 0) {
            cout << "LCM: " << maximum << endl;
            break;
        }
        maximum++;
    }
}

이 프로그램은 두 수 중 더 큰 값부터 시작하여, 두 수 모두로 나누어 떨어지는 첫 번째 수를 찾을 때까지 1씩 증가시키며 확인합니다. 실행 결과는 다음과 같습니다.

LCM: 20

문제 해결 접근 방식

세 수의 LCM을 최대로 만들려면 가능한 한 N에 가까운 수들을 선택하면서, 동시에 수들 사이에 공약수가 생기지 않도록 해야 합니다. 이 아이디어를 바탕으로 한 알고리즘은 다음과 같습니다.

N이 홀수인 경우: N, N-1, N-2가 답입니다. 세 수가 서로소이므로 LCM은 세 수의 곱과 같습니다.
N이 짝수이고 N과 N-3의 최대공약수(GCD)가 1인 경우: N, N-1, N-3이 답입니다. N이 짝수면 N과 N-2가 공약수 2를 공유하기 때문에 N-2 대신 N-3을 고려합니다.
그 외의 경우: N-1, N-2, N-3이 답입니다.

구현 예제

위 알고리즘을 C++ 코드로 구현하면 다음과 같습니다.

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

void threeNumbersWithMaxLCM(int n) {
    if (n % 2 != 0) {
        // N이 홀수인 경우
        cout << n << " " << (n - 1) << " " << (n - 2);
    } else if (__gcd(n, n - 3) == 1) {
        // N이 짝수이고 N과 N-3이 서로소인 경우
        cout << n << " " << (n - 1) << " " << (n - 3);
    } else {
        // 그 외의 경우
        cout << (n - 1) << " " << (n - 2) << " " << (n - 3);
    }
    cout << endl;
}

int main() {
    int n = 18;
    threeNumbersWithMaxLCM(n);
    return 0;
}

실행 결과

위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.

17 16 15

N = 18은 짝수이고, gcd(18, 15) = 3으로 1이 아니므로 세 번째 경우에 해당합니다. 따라서 답은 17, 16, 15이며, 이 세 수는 서로소이므로 LCM은 17 × 16 × 15 = 4080이 됩니다.

참고로 N이 3보다 작은 경우에는 위 로직이 음수를 출력할 수 있으므로, 실제 문제 풀이 시에는 N의 크기에 따른 예외 처리를 추가하는 것이 좋습니다.

마무리

이번 튜토리얼에서는 LCM의 기본 개념부터 시작해, N 이하의 세 정수 중 LCM이 최대가 되는 조합을 찾는 효율적인 방법까지 살펴보았습니다. 내용에 대해 궁금한 점이 있다면 댓글로 남겨주세요.