https://www.acmicpc.net/problem/2609
문제 해결 일자 : 2024.10.08(화)
난이도 : 브론즈 1(Solved.ac)
문제 풀이 / 코드 구현 : 알고리즘 참고를 위해 검색(구글링) / 직접
더보기
카테고리 : 수학 , 정수론 , 유클리드 호제법
문제 내용 : 입력으로 두 정수가 들어올때, 두 수의 최대 공약수와 최소 공배수를 출력하면된다.
문제 풀이 :
최대 공약수를 구하기 위해서 소인수분해를 하게 되면 시간복잡도에 걸리게 된다
유클리드 호제법 이라는것을 사용하면 시간복잡도만 잡을뿐만 아니라 최소공배수도 같이 계산이된다.
이렇게 문장으로 보게되면 무슨말인가 부터 의문이 들지만, 이해하면 정말 간단한 말이다.
진짜 중요한 문장은 이 문장이다.
우리는 반복문으로 나머지가 0일때까지 루프를 돌리다
r=0이 되는 구간이 나오면 b를 최대공약수로 선택하면된다.
유클리드 호제법 활용 예시)
최소공배수는 (a*b) / gcb(a,b)를 하면 나온다.
접근 순서 :
1) 큰수가 작은수를 나눌수 있게 두 정수(a,b)의 대소비교를 한다.
2) 두 정수(a,b)의 /(몫) , %(나머지) 연산 계산을 한다.
3-1) 나머지가 0이 아닌 경우 a,b를 초기화 한다.
a = 두 숫자중 작은숫자(b)
b = 두숫자의 나머지(r)
3-2) 나머자기 0인경우 해당 b를 최대공약수로 선언한뒤 반복문을 탈출한다.
4) 1)과정으로 돌아가 반복한다. 반복문을 탈출한 경우이면 최소공배수 계산을 한다.
구현코드 :
더보기
#include <iostream>
#include <string>
using namespace std;
void Swap(int& num1, int& num2)
{
int tmp = num1;
num1 = num2;
num2 = tmp;
}
int main(void)
{
int num1, num2;
cin >> num1 >> num2;
int oldnum1 = num1;
int oldnum2 = num2;
int result = 0;
int remainder = 1;
int gcb = 0;
while(remainder != 0)
{
if(num1 <num2)
{
Swap(num1,num2);
}
result = num1 / num2;
remainder = num1 % num2;
if(remainder == 0)
{
gcb = num2;
break;
}
num1 = num2;
num2 = remainder;
}
cout << gcb <<endl;
cout << (oldnum1 * oldnum2) / num2;
return 0;
}