[백준] 2609 최대공약수와 최소공배수_ JAVA

● 문제

 

---

● 풀이

이 문제를 풀이하기 전에 BigInteger 클래스에 대해 개념을 정리하였는데, BigInteger 자체 최대 공약수를 계산하는 유틸리티 메서드가 존재하였다. 최대 공약수만 있으면 이로 최대 공배수를 계산할 수 있기에 바로 적용해보았다.

 

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        BigInteger numA = BigInteger.valueOf(in.nextInt());
        BigInteger numB = BigInteger.valueOf(in.nextInt());

        BigInteger gcd = numA.gcd(numB);
        BigInteger lcm = numA.multiply(numB).divide(gcd);

        System.out.println(gcd);
        System.out.println(lcm);
    }
}

백준 풀이는 성공하였지만, 메모리와 시간이 흔히 쓰는 코드와 확연히 차이가 났다...

그냥 있는 정도만 알면 될듯

그래도 넘 쉬워지는데....

 

---

흔히 쓰는 최대공약수, 최소공배수 코드

import java.util.Scanner;
 
public class Main {
 
	public static void main(String[] args) {
 
		Scanner in = new Scanner(System.in);
		
		int a = in.nextInt();
		int b = in.nextInt();
 
		int d = gcd(a, b);	// 최대공약수
 
		System.out.println(d);
		System.out.println(a * b / d);
 
	}
 
	// 최대공약수 재귀 방식
	public static int gcd(int a, int b) {
		if (b == 0)
			return a;
            
		// GCD(a, b) = GCD(b, r)이므로 (r = a % b)
		return gcd(b, a % b);
	}
}

출처 : https://st-lab.tistory.com/154

[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]