백준 1934 - java

문제

 

내풀이

 

import java.util.Scanner;

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

        for (int i = 0; i < N; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();

            int lcm = Math.min(A, B);
            while (true) {
                if (lcm % A == 0 && lcm % B == 0) {
                    System.out.println(lcm);
                    break;
                }
                lcm++;
            }
        }
    }
}

이렇게 풀었더니 실행 시간 오류가 떳다.  두 수 A와 B가 큰 수인 경우 lcm 값을 일일이 증가시키면서 A와 B로 나누어떨어지는지 확인하는 과정이 매우 오래 걸릴 수 있다. 특히 A와 B가 서로 소수인 경우, 이 과정은 최악의 경우 두 수의 곱까지 반복해야 할 수도 있다.

 

 

import java.util.Scanner;

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

        for (int i = 0; i < N; i++) {
            int A = sc.nextInt();
            int B = sc.nextInt();

            int gcd = gcd(A, B);
            int lcm = (A / gcd) * B;
            System.out.println(lcm);
        }
    }

    public static int gcd(int a, int b) {
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        return a;
    }
}

최소공배수를 구한다.