세 수의 최대공약수(GCD)와 최소공배수(LCM) 구하기

이번엔 두 수가 아닌 세 수의 GCD와 LCM을 구하는 방법에 대해 정리했다.
처음에는 헷갈렸지만, 기본적인 GCD/LCM 개념을 그대로 확장하면 된다는 걸 깨달았다.

📌 문제

세 개의 자연수 A, B, C가 주어졌을 때,

세 수의 최대공약수(GCD)

세 수의 최소공배수(LCM)
을 구하는 문제다.

🧠 핵심 아이디어
GCD와 LCM은 기본적으로 두 수에 대해 정의된 연산이다.
그래서 세 수 이상에 대해 구하려면, 두 수씩 계산을 이어가면 된다.
예를 들어,

GCD(A, B, C) = GCD(GCD(A, B), C)
LCM(A, B, C) = LCM(LCM(A, B), C)

이런 방식으로 차례대로 계산하면 된다.

using System;

class Program
{
    static void Main()
    {
        int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
        int a = input[0];
        int b = input[1];
        int c = input[2];

        int gcd = GCD(GCD(a, b), c);
        int lcm = LCM(LCM(a, b), c);

        Console.WriteLine(gcd);
        Console.WriteLine(lcm);
    }

    static int GCD(int a, int b)
    {
        while (b != 0)
        {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }

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

💡 배운 점

GCD(GCD(a, b), c) → 앞의 결과를 다음 수와 또 GCD로 계산한다.

LCM(LCM(a, b), c)도 마찬가지로 두 수씩 계산을 이어나간다.

유클리드 호제법은 여전히 강력하고 효율적인 알고리즘이라는 걸 다시 느꼈다.

📌 정리

유클리드 호제법처럼 기본적인 알고리즘은
직접 구현해보고 몸에 익혀두자.
그러면 새로운 문제에서도 빠르게 적용할 수 있다!