백준, BOJ, 2609번 C++ [CPP]

이문제는 유클리드 호제법을 이용하면 쉽게 풀 수 있다.

풀어보자

 

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

 

 

---

 

 

#맞는 풀이

#include<iostream>

using namespace std;

int gcd(int a, int b)
{
	int c;
	while (b != 0)
	{
		c = a % b; //나머지
		a = b; // 몫이 다시 피제수로
		b = c; // 나머지가 제수로
	}
	return a;
}


int main(){
    int p,q;
    cin >> p >> q;
    int g = gcd(p,q);
    cout << g << '\n';
    cout << (p*q)/g << '\n';
}

 

A = Ga, B= Gb라 한다면

G는 최대공약수이고

Gab는 최소공배수이다.

 

여기서 중요한 점은 p,q가 순서가 바뀌어도 똑같다는 점이다.

즉, 크기를 구분않고 넣어도 된다.

 

 

37,64순으로 넣든 64,37을 넣든 똑같다고???

64%37 이나 37%64나 같을 결과를 보여준다는 것인데..?

64%37 == 27 이다. 37%64 == 37이다???

다른데...?

 

하지만 while문 안에 들어가면

37,64의 경우

c = 37

a = 64

b = 37

이된다.

 

64,37의 경우

c = 27

a = 37

b=27이 된다.

 

 분명 다르다..

하지만 두번째 하면 알 수 있는데

37,64의 경우 2번째는

c = 27

a = 37

b = 27

이된다.

즉, 한바퀴 더 돌뿐이지 같아진다.

 

유클리드호제법에서도 a>b일 때임이 조건으로 붙어있다.

값이 같은 이유는 유클리드 호제법에서 교환을 허용하기 때문이 아니라.

while문을 돌면서 알아서 다시 크기를 바꿔주기 때문이라고 말할 수 있다.

 

하지만 불안하면 따로 조건을 만들어주자.