[C#] 13241번: 최소공배수

목차

---

백준 단계별로 풀어보기

25.11.06

15단계: 약수, 배수와 소수 2

13241번: 최소공배수

문제 링크 : https://www.acmicpc.net/problem/13241

 

문제를 풀기 위해 알아야 할 개념

>> 유클리드 호제법

: 아래 링크에 정리해두었다.

 

유클리드 호제법을 활용하여 최대공약수, 최소공배수 구하기

 

문제 풀이

: 유클리드 호제법을 활용하여 최대공약수를 구하고, 최대공약수를 활용하여 최소공배수를 구한다. (재귀함수 형태로 풀어보았다.)

--> 최소공배수를 구하기 위해 두 입력값을 곱할 때, 입력값의 최댓값이 10⁸ 보다 작은 값이므로 int 자료형으로는 담을 수 없기에 long 자료형을 사용한다.

1. StreamReader로 입력값을 받아 각각 long값으로 변환하여 정수를 담을 변수 a 와 b 에 담는다.
2. 삼항연산자를 활용하여 a 와 b 를 비교하고, 그에 맞게 유클리드 호제법을 활용하여 만든 GCD 함수에 넣어 최대공약수를 계산하고 변수 gcd 에 담는다.
3. 계산한 최대공약수를 활용하여 최소공배수를 구하여 출력한다.

 

정답 코드

using System.IO;

class Backjoon
{
    static void Main(string[] args)
    {
        using var sr = new StreamReader(Console.OpenStandardInput());
        using var sw = new StreamWriter(Console.OpenStandardOutput());

        string[] input = sr.ReadLine().Split();
        long a = long.Parse(input[0]);
        long b = long.Parse(input[1]);

        long gcd = a > b ? GCD(a, b) : GCD(b, a);
        
        sw.Write(a * b / gcd);
    }

    static long GCD(long a, long b)
    {
        if (b == 0)
            return a;
    
        return GCD(b, a % b);
    }
}