[백준/실버5] 백준 13241번 최소공배수 - c++ / 유클리드 호제법(최대공약수, 최소공배수) 문제 해석/코드 설명

[백준/실버5] 백준 13241번 최소공배수 - c++ / 유클리드 호제법(최대공약수, 최소공배수)

 

코딩테스트 타파하기 1주차 - 1번

주요 키 포인트

유클리드 호제법 (최대공약수)

2개의 자연수(또는 정수) a,b에 대해서 a를 b로 나눈 나머지를 r이라고 하면 (이때, a>b), a와 b의 최대 공약수는 b와 r의 최대공약수와 같다. 아래의 코드를 살펴보면

int gcd(long long int a, long long int b){ 
    if(b==0) return a;
    return gcd(b, a%b);
}

 

연쇄적으로 최대공약수를 찾아가는 것을 볼 수 있다. 성질에 따라서 b를 r로 나눈 나머지를 구하고 다시 이것들을 연쇄적으로 진행해서 나머지가 0이 되었을 때 나누는 수 ((a%b)에서 b)가 a와 b의 최대공약수이다.

 

예) 

gcd(30, 24) 

a : 30 b : 24

a : 24 b: 6 

a : 6 b : 0

즉 최대 공약수 6이 나오게 된다.

 

최소공배수 : a*b / gcd(a,b )

예)

gcd(20, 10)

a : 20 b : 10

a : 10 b : 0 

즉 최대 공약수 10

20*10 / 10 = 20

즉 최소 공배수 20

 

#include <iostream>

using namespace std;

int gcd(long long int a, long long int b){ 
    if(b==0) return a;
    return gcd(b, a%b);
}

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); cout.tie(nullptr);
    
    long long int x=0,y=0;
    cin >> x>>y;
    long long int num = gcd(x,y);
    cout << x*y/num;
    
    return 0;
}

 

조건 : C/C++에서는 long long int를 사용