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

목차

---

백준 단계별로 풀어보기

25.11.05

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

1934번: 최소공배수

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

 

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

>> 유클리드 호제법 (Euclidean Algorithm)

: 두 자연수의 최대공약수를 구하는 알고리즘. 이때 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.

--> 두 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

 

- 반복문을 활용한 코드

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

    return a;
}

 

- 재귀함수를 활용한 코드

// a > b
int GCD(int a, int b)
{
    if (b == 0)
        return a;
    
    return GCD(b, a % b);
}

 

※ 참고 문서 - 위키백과

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

 

>> 최대공약수(GCD)를 활용하여 최소공배수(LCM) 구하기

: 최소공배수(Least Common Multiple)는 최대공약수(Greatest Common Divisor)를 활용하여 아래 식으로 바로 구할 수 있다.

→ 최소공배수 = 두 자연수의 곱 / 최대공약수

 

※ 참고 블로그

[알고리즘] 최대공약수(GCD), 최소공배수(LCM), 유클리드 호제법

 

문제 풀이

: 유클리드 호제법을 활용하여 최대공약수를 구하고, 최대공약수를 활용하여 최소공배수를 구한다.

1. StreamReader로 입력값을 받아 int값으로 변환하여 테스트 케이스의 개수를 담을 변수 count 에 담는다.
2. for 반복문을 통해 최소공배수를 구한다.
   •     StreamReader로 두 자연수를 입력 받아 각각 int값으로 변환하여 변수 a 와 b 에 담는다.
   •     삼항연산자를 활용하여 a 와 b 를 비교하고, 그에 맞게 유클리드 호제법을 활용하여 만든 GCD 함수에 넣어 최대공약수를 계산하고 변수 gcd 에 담는다.
   •     계산한 최대공약수를 활용하여 최소공배수를 구하고 StringBuilder에 담는다.
3. StringBuilder에 담은 값을 출력한다.

 

정답 코드

using System.IO;
using System.Text;

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

        int count = int.Parse(sr.ReadLine());

        for (int i = 0; i < count; i++)
        {
            string[] input = sr.ReadLine().Split();
            int a = int.Parse(input[0]);
            int b = int.Parse(input[1]);
            
            int gcd = a > b ? GCD(a, b) : GCD(b, a);

            sb.AppendLine((a * b / gcd).ToString());
        }
        sw.Write(sb.ToString());
    }

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

        return a;
    }
}