두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.
첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 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;
}
항상 근본 원리에 대한 감을 익혀두고, 문제가 나오면 추론하고자 하는 성향이다. 하지만 이건 그냥 외워두는 편이 속 편할 것 같다.