공부방

문제 설명에서 알 수 있듯이, 유클리드 호제법을 이용해 최소공배수를 구하는 문제이다. 먼저 유클리드 호제법에 대해 알아보자. 유클리드 호제법을 이용해 최대공약수를 구할 수 있다. 최대공약수를 구하면 자연스럽게 최소공배수도 구할 수 있는데, 예를 들어 35와 100의 경우 100을 35로 나눈 나머지 -> 30 35를 30으로 나눈 나머지 -> 5 30을 5로 나눈 나머지 -> 0 따라서 최대공약수는 5가 되고, 이를 이용해 최소공배수를 구하면 35 x 100 / 5 = 700 이 된다. 먼저 유클리드 호제법을 이용해 최대공약수를 구하는 식은 다음과 같다. long a = sc.nextInt(); long b = sc.nextInt(); long gcd = 0; // 최대공약수 if (a > b) { lo..

주어진 a와 b값의 최소공배수를 구하는 문제이다. 최소공배수는 a와 b의 공배수 중 가장 작은 수이므로 단순히 두 수중 큰 수부터 시작하여 하나씩 비교하는 방식으로 쉽게 구할 수 있다. 위와 같이 먼저 a와 b의 값을 비교하여 큰 수를 b쪽에 두고, while문을 이용하여 b값을 시작값으로 두고 1씩 증가시키면서 조건(공배수)을 만족시키는 값을 찾을 수 있다. 다만 이렇게 구하게 되면 시간이 굉장히 오래걸리기 때문에 위와 같은 코드로 제출하게 되면 시간 초과라는 오류가 발생하게 된다. 따라서 조금 다른 방식으로 구해보았다. 최소공배수는 두 수의 곱 / 최대공약수 로 구할 수 있기 때문에 먼저 최대공약수를 구한다. 최대공약수는 1부터 두 수중 작은 수까지로 한정되어 있기 때문에 비교적 짧은 시간에 값을 구..