반응형
https://www.acmicpc.net/problem/1934
- 문제
두 수가 주어지면 두 수의 최소 공배수를 구하는 문제다.
- 해설
유클리드 호제법이라는 것을 알게 되었는데, 이것을 이용하면 최소공배수, 최대공약수 문제가 쉽게 풀린다.
- 풀이
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int x, int y)
{
return (x % y == 0) ? y : gcd(y, x % y);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int T, A, B;
cin >> T;
for (int i = 0; i < T; i++)
{
cin >> A >> B;
if (A >= B)
cout << A * B / gcd(A, B) << '\n';
else
cout << A * B / gcd(B, A) << '\n';
}
return 0;
}
- 새롭게 알게 된 점
유클리드 호제법
int gcd(int x, int y)
{
return (x % y == 0) ? y : gcd(y, x % y);
}
1. x와 y로 나눈다
- 나눠지면 y가 최소공배수
- 아니면 y의 최소공배수를 구하러 감
2. y와 x%y를 나눈다.
- 나눠지면 x%y가 최소공배수
- 아니면 반복
반응형
'Algorithm > Baekjoon BOJ' 카테고리의 다른 글
[백준][C++] 3036 : 링 (0) | 2022.10.21 |
---|---|
[백준][C++] 2981: 검문 (0) | 2022.10.21 |
[백준][C++] 5086 : 배수와 약수 (0) | 2022.10.21 |
[백준][C++] 1358 : 하키 (0) | 2022.10.21 |
[백준][C++] 2477 : 참외밭 (0) | 2022.10.21 |