백준 2609 최대공약수와 최소공배수(Java)

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

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

---

 

해석 및 팁

 

---

 

이 문제를 풀때 for문을 통해서도 풀수있지만 백준에서는 시간초과로 인해 틀리게 됩니다. 간단하게 푸는 방법은 BigInteger 클래스에서 사용가능한 gcd를 사용하면 됩니다. 두 수를 입력받은후 BigInteger형식으로 변경시켜주고 gcd함수를 사용한후 Int형으로 바꿔주면 최대공약수가 나오게 됩니다. 두 값의 곱은 최대공약수와 최소공배수의 곱과 같으므로 두 값의 곱에 최대공약수를 나누어주면 최소공배수가 나옵니다.

 

 

---

 

Java 코드

 

---

import java.util.Scanner;
import java.math.BigInteger;                       //BingInteger을 사용하기위해 import 해준다

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

    int a = sc.nextInt();
    int b = sc.nextInt();
    BigInteger a1 = BigInteger.valueOf(a);           //BigInteger타입으로 변환
    BigInteger b1 = BigInteger.valueOf(b);
    int g = a1.gcd(b1).intValue();                   //int 형으로 변환시켜준다
    int l = a * b / g;

    System.out.println(g);
    System.out.println(l);
  }
}