C++) 백준 1934번: 최소공배수(유클리드 호제법)

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

< 접근 방식 1 - 성공 >

처음 문제를 보자마자 생각이 난 풀이는 고전적인 풀이법이었다.

많이들 알고 있는 풀이일 것이다. 해당 풀이대로 구현을 하니 꽤나 복잡했다.

아래는 코드이다.

 

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int T;
cin >> T;

int A, B;
for (int i = 0; i < T; i++) {
cin >> A >> B;
int A_tmp = A, B_tmp = B;
int div_mult = 1, flag = 0;
if (A == 1)
cout << B << endl;
else if (B == 1)
cout << A << endl;
else {
while (1) {
int div = 2;
while (1) {
if (A_tmp % div == 0 && B_tmp % div == 0) {
A_tmp /= div;
B_tmp /= div;
div_mult *= div;
break;
}
else {
div++;
if (div > A_tmp || div > B_tmp) {
flag++;
break;
}
}
}
if (flag > 0)
break;
}
cout << div_mult * A_tmp * B_tmp << endl;
}
}

return 0;
}

풀기는 했으나.. 중간에 하면서도 이중반복문 때문에 시간초과가 나지는 않을까? 걱정을 하기도 했었다. 하여 다른 풀이가 있을까 찾아보던 와중, 최대공약수와 관련하여 유클리드 호제법이라는 기가 막히고 코가 막히는 방법을 알게 되었다. 들어본 적은 있는데 한 번도 이용해 본 적은 없는 것 같다.

 

< 접근 방식 2 - 성공 >

큰 수를 작은 수로 나누고 나머지가 0이 되면 해당 작은 수를 리턴, 0이 되지 않으면 해당 작은 수와 나머지로 이전 단계를 다시 시행한다.

재귀적인 움직임이 딱 보여서 재귀함수로 구현.

아래는 코드이다.

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

int gcd(int A, int B);

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);

int T;
cin >> T;

int A, B;
for (int i = 0; i < T; i++) {
cin >> A >> B;
cout << (A * B) / gcd(A, B) << endl;
}

return 0;
}

int gcd(int A, int B)
{
int r = A % B;
if (r == 0)
return B;
else
return gcd(B, r);
}

 

다양한 시각으로 문제를 풀어보는 것이 좋은 것 같다. 이렇게 하다보면 최적의 효율을 찾을 수 있는 내가 되지 않을까?