백준 1934번 최소공배수 [C언어]

문제 출처: https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

 

Sol)

#include <stdio.h>

int main(){
    int tc;
    int num1, num2, gcd, lcm;

    scanf("%d", &tc);

    while(tc--){
        scanf("%d %d", &num1, &num2);

        int bigger = num1 > num2 ? num1 : num2;
        int smaller = num2 > num1 ? num1 : num2;
        int temp;

        while(smaller > 0){
            temp = bigger;
            bigger = smaller;
            smaller = temp % smaller;
        }
        gcd = bigger;

        lcm = num1 * num2 / gcd;

        printf("%d\n", lcm);
    }

    return 0;
}

 

• 풀이 방향

최소 공배수를 쉽게 구하기 위해서는 최대 공약수를 구한 뒤, 두 수의 곱을 최대 공약수로 나눠주면 되겠다. 왜 이렇게 되는지 간단하게 설명해 보자면,

A = g * a, B = g * b 라 하자.

A와 B의 최소 공배수는 g * a * b 이다.

이는 A * B = g^2 * a * b 를 두 수의 최대 공약수인 g로 나눈 값과 같다.

 

• 풀이

먼저, 유클리드 호제법을 이용해 두 수의 최대 공약수를 구해준 뒤, 두 수의 곱을 이로 나눠 주었다.

 

• 문제에 대한 사견

유클리드 알고리즘만 알고 있다면 어려운 문제는 아니었다.

 

 

https://csloth.tistory.com/28

유클리드 호제법(Euclidean algorithm)