https://www.acmicpc.net/problem/2609
문제
> 두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.접근
유클리드 호제법을 사용하여 두 수의 최대 공약수를 먼저 구하고 두 수의 곱을 최대 공약수로 나눈 값이 최소 공배수이기 떄문에 이를 계산해 구해준다.
문제해결
> 두 수가 주어졌을 때 a를 b로 나눈 나머지를 r이라고 했을 때,
이 r이 0이 될 때 까지 다시 b를 r로 나누는 반복과정을 유클리드 호제법 이라고 한다.
> main에서 두 수를 입력받고 이 두수를 인자로 GCD메소드에 넣어 호출해준다.
> 최소 공배수를 위해 먼저 두 수의 곱을 구해 놓고, gcd연산을 통해 r이 0이 되어 b에 0이 전달 될 때까지 반복한다.
> 이 때의 a값이 r이 0이 나왔을 때의 b값이 전달된 값이므로 이 값을 최대 공약수로 가진다.
> 그리고 두 수의 곱을 최대공약수로 나눈 값이 최소공배수 이므로 이를 계산해 출력한다.코드
import java.io.*;
import java.util.*;
import java.lang.*;
public class Main
{
//2609번 최대공약수와 최소공배수
static void GCD(int a, int b)
{
int mul = a * b;
while(b > 0)
{
int r = a % b;
a = b;
b = r;
}
System.out.println(a + "\n" + mul / a);
}
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
GCD(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
}
}
후기
지금 까지 유클리드 호제법을 사용하기 위해선 두 수 a,b에 대해서 반드시 a>b를 만족해야한다는 선행 조건이 있는걸로 알고 있었다. 그래서 매번 swap기능을 넣어 b가 더 클떄 이를 바꾸고 시작해줬다. 하지만 이런 조건은 없다고 하며, 있다고 한들 어차피 예를 들어 10, 12에 대해선 a % b하면 r은 10이 그대로 나오고 a에 12, b에 10이 들어가면서 두 수가 바뀌게 된다. 이 문제를 통해 내가 아직 유클리드 호제법 동작의 세부적인 부분을 전부 파악하지 못하다는걸 알았다.
