[백준] - 최소 공배수 (13241) (자바/Java)

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

문제.

---

 

 

 

 

 

 

 

풀이.

---

 

public class Main {
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();

        System.out.println(a * b / Gcd(a, b));

    }

    static long Gcd(long a, long b) {
        while (b != 0) {
            long temp = a % b;
            a = b;
            b = temp;
        }
        return a;
    }

}

 

이번 문제는 "최소 공배수" 구하는 문제다.

지난번에도 최소 공배수 문제를 푼 적이 있는데 "유클리드 호제법"을 참고해 풀면 어렵지 않은 문제라 생각한다.

그럼 바로 풀이를 해보겠다.

 

1. 문제에 입력 숫자가 크므로 int로 할경우 에러가 날 거다. 그러므로 long타입으로 입력해줘야 한다.

 

2. 다음 유클리드 호제법을 사용해 최소공배수를 구하면 끝이다.

 

사실 앞에 말했다 시피 유클리드 호제법을 알면 쉽게 접근할 수 있는 문제다.

그래서 밑에 유클리드 호제법 정리한 링크도 남겨두겠다.

https://luke-king.tistory.com/42

[백준] - 최대공약수와 최소공배수 (2609) (자바/Java)