[코딩테스트] 백준 #2609 문제 풀이

먼저 이 문제를 풀기 위해서는 '유클레드 호제법' 알고리즘을 알아야 한다.

유클레드 호제법을 이용하여 최대공약수를 구할 수 있는데, 이는 반복문을 이용하면 된다.

위에 메모장에 끄적한 것이 유클레드 호제법을 이용한 최대공약수 구하기의 대략적인 설명이다.
먼저 큰 수를 작은 수로 나눈다. 위 예시를 보면 35를 28로 나누고 나머지가 7이 남는다. 다음으로 나눈 수인 28을 나머지로 나눈 나머지를 구해본다. 나머지가 0이 되었다. 이렇게 되면 그 직전 식에서 나눈 수였던 7이 이 두 수의 최대공약수가 되는 것이다.

한마디로 나머지가 0이 될 때까지 무한 반복을 하면 되는 것이다. 나머지가 0이 되는 순간 반복문은 종료된다. 여기서도 swap함수를 적용해야 한다.

최대공약수를 구했다면 최소공배수를 구하는 것은 쉽다. 최대공약수로 각각 입력받은 수를 나누어 최대공약수 값과 나눈 각각의 수를 모두 곱해주면 되는 것이다.

코드는 다음과 같다.

최종 코드

#include <iostream>

using namespace std;

int GCD(int a, int b)
{
    int c;
    while(b != 0)
    {
        c = a % b;
        a = b;
        b = c;
    }
    return a;
}

int main()
{
    int number1, number2;
    
    cin >> number1 >> number2;
    
    int gcd = GCD(number1, number2);
    
    int lcm = gcd * (number1 / gcd) * (number2 / gcd);
    
    cout << gcd << endl;
    cout << lcm << endl;
}