[백준] 2609번 최대공약수와 최소공배수

 

 

문제

소스코드

지우지 말고 이 폰트로 글을 작성할 것!(폰트가 사라짐)

 

#include<iostream>
 
int GCD(int lhs, int rhs) {
    //lhs에 큰값
    if (rhs > lhs) {
        std::swap<int>(rhs, lhs);
    }
    
    while (rhs != 0) {
        int n = lhs % rhs;
        lhs = rhs;
        rhs = n;
    }
    return lhs;
}
 
int LCM(int lhs, int rhs) {
    return lhs*rhs / GCD(lhs, rhs);
}
 
int main() {
    int lhs{}, rhs{};
    std::cin >> lhs>>rhs;
 
 
    std::cout << GCD(lhs, rhs) << "\n";
    std::cout << LCM(lhs, rhs) << "\n";
 
}

 

후기

이 문제를 해결하기 위한 키워드는 유클리드 호제법이다.

 

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 

lhs, rhs 두 개의 정수가 있으며 lhs> rhs라는 가정하에 lhs를 rhs로 나눈 나머지 값이 N이라고 하면 lhs와 rhs의 최대공약수는 rhs와 N의 최대공약수와 같다는 성질을 이용해서 rhs의 나머지가 0이 될 때까지 이 과정을 반복하며 나오는 값이 lhs과 rhs의 최대공약수이다.

 

최소공배수는 이 GCD 값을 lhs*rhs 으로 나누면 된다.

 

알고리즘 자체는 어렵지 않지만 짧은 시간 안에 많은 문제를 풀어야 했던 회사 시험 문제에 나왔던 기억이 나서 다시 풀어보았다.

 

 

출처 및 레퍼런스

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

 

관련 글

Wiki:https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95