백준 2609 - 최대공약수와 최소공배수

LeeTaeHwa·2022년 3월 11일
0

알고리즘

목록 보기
1/6

문제


두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력


첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력


첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

해설


분명히 옛날에 푼적이 있는데, 다시 보니까 까먹어 버렸다. 어떻게 풀어야 할지 대충은 감이 오지만, 결국 좀 더 우아한 방법을 찾아 구글님께 물어봐버렸다.

문제의 핵심은 GCD(Greatest Common Divisor)LCM(Least Common Multiple)을 어떻게 해결하느냐다. GCD는 유클리드 호제법을 이용하여 구하면 되고, LCM은 앞서 구한 GCD를 이용하여 두 수의 곱 / GCD를 하면 바로 구할 수가 있다.

그렇다면 유클리드 호제법은 무엇인가? 2개의 자연수에 대한 최대 공약수를 구하는 알고리즘이다. 알고리즘의 내용은 딱히 어려울 것이다 없다. 그냥 두 자연수를 가지고 계속 나머지 연산을 하면 된다.

길게 말해 뭐하겠는가, 코드부터 보도록 하자.

auto eucludean(int left, int right) -> int {
    while(right != 0) {
        auto tmp = left % right;

        left = right;
        right = tmp;    
    }

    return left;
}

나누기에 사용한 값과 나머지 연산으로 나온 값을 계속 사용하여 나누어 떨어질 때까지 반복한다. 그러고 난 다음에는 간단하다.

auto main(int argc, char* argv[]) -> int {
    auto n = 0;
    auto m = 0;

    std::cin>>n>>m;

    auto gcd = eucludean(n, m);
    auto lcm = n * m / gcd;

    std::cout<<gcd<<std::endl;
    std::cout<<lcm<<std::endl;

    return 0;
}

항상 근본 원리에 대한 감을 익혀두고, 문제가 나오면 추론하고자 하는 성향이다. 하지만 이건 그냥 외워두는 편이 속 편할 것 같다.

profile
하늘을 향해 걸어가고 있습니다.

0개의 댓글