[java 백준] 실버 5/ 1934번 최소 공배수

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

1934번: 최소공배수

import java.util.Scanner;
 
public class Main {
 
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
 
        int num = sc.nextInt();
        for (int i = 0; i < num; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            if (a > b) {
 
                int mul = gcd(a, b);
                a = a / mul;
                b = b / mul;
                System.out.println(b * a * mul);
            } else if (b > a) {
                int mul2 = gcd(b, a);
                a = a / mul2;
                b = b / mul2;
                System.out.println(b * a * mul2);
            } else if (a == b) {
                System.out.println(a);
            }
 
        }
 
    }
 
}

 

이 문제는 최대공약수를 구하는 유클리드 호제법을 사용해야 한다!

 

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=shalska1234&logNo=50086379449 

유클리드 호제법(Euclidean algorithm)에 대하여~

위의 블로그를 참고해서 이해를 해봤다! (더 알아보고 싶으신 분은 url타고 가보세요!)

 

예를 들어 2004 와 98의 최대공약수를 구한다고 해보자.

 

2004를 98로 나눈 나머지는 44이다.

 

(2004,98)=(98,44)

-->(나뉘는 수, 나눈 나머지)

 

 

98을 44로 나눈 나머지는 10이다

(2004,98)=(98,44)=(44,10)

 

44를 10으로 나눈 나머지는 4이다.

 

(2004,98)=(98,44)=(44,10)=(10,4)

 

10을 4로 나눈 나머지는 2이다.

 

(2004,98)=(98,44)=(44,10)=(10,4)=(4,2)

 

4를 2로 나눈 나머지는 0이다.

 

(2004,98)=(98,44)=(44,10)=(10,4)=(4,2)=(2,0)

 

 

결론적으로 2004와 98의 최대공약수는 2이다.

 

---

 

유클리드 호제법을 코드로 옮겨보면 

 

public static int gcd(int a, int b) {

        if (b == 0) {

            return a;

        } else {

            return gcd(b, a % b);

        }

    }

 

나머지가 0 이면 함수를 빠져나오고, 나머지가 0이 아니면 gcd(나뉘는 수 ,a를 b로 나눈 나머지) 로 리턴해준다.