Baekjoon 2609 최대공약수와 최소공배수 JAVA

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

2609번: 최대공약수와 최소공배수

https://github.com/JUNGSOONIL/JAVA/blob/main/BAEKJOON%202609

GitHub - JUNGSOONIL/JAVA: JAVA 소스 코드

 

해당 문제는 두 수가 주어졌을 때 최대 공약수와 최소 공배수를 구하는 문제다.

 

예전에 수업중에 최소 공배수에 대해서 구하는 방법에 관한 방법을 얼핏 배웠던 게 기억이 나서 한번 풀어보면서

관련된 방법들을 좀 알아보고자 해당 문제를 풀어보게 되었다.

 

처음에 문제를 보고 음 수업 방법말고 어떻게 구했던지 가물가물해서 친구한테 물어봤더니

연제 법이라는 방법을 알려줬는데

두 수를 공통된 약수로 나눠질 때까지 나누고 난 뒤 공통된 약수를 곱하면 최대 공약수가 되며

공통된 약수 * 나눈 나머지를 곱하게되면 최소 공배수가 된다고 한다.

 

일단 저 방법이 있었고 수업때 배운 부분은 먼저 큰 수에서 작은 수를 나눠주고, 이제 작은 수에 그 나눈 값을

계속 나눠줘서 0이되면 이때 그 작은 수가 최대 공약수가 되며, 최소 공배수의 경우

두 수를 곱한 뒤 최대 공약수를 나눈 몫을 구하면 해결 가능하다.

 

입력 값을 받으면서 먼저 두수중 큰 값을 앞에 저장하는 방식으로 로직을 짜서 문제를 해결했는데,

알고 보니 해당 부분은 불필요한 부분이었다.

 

이후 최대 공약수를 구해주는데 여기서 두 수를 넣어준 뒤 반복문을 통해 b가 0이 될 때까지 반복하며,

c에는 a% b값을 넣어주고, a값은 더 이상 필요 없으므로 b값으로 바꿔주고

b를 c로 바꿔준 뒤 반복문을 계속해서 b가 0이 되었을 때 a값이 최대 공약수가 된다.

 

최대 공약수를 구하면 최소 공배수는 위에서 말했듯이 두 수를 곱한 뒤 최대 공약수를 나눈 몫을 출력하면 된다.