[백준] JAVA 자바 : 최소공배수 (1934번)

---

앞에서 GCD와 LCM을 찾는 문제를 풀었지만…
문제를 다시 보니 이상하게 나만 300ms대가 나오는 것이었다… 분명 다른 분들은 80~150ms가 걸리시는데… 왜 나만 이렇게 비효율적이게 돌아가는 거지??

그래서 다른 분들의 코드를 참조했는데, 나는 바보같이 for문을 계속 돌려서 GCD와 LCM을 찾았지만 유클리드 호제법으로 더 간단하게 GCD와 LCM을 찾을 수 있었다.

유클리드 호제법

GCD: 두 수 a와 b를 받으면, a에서 b를 나눈 나머지가 0이될 때의 b가 GCD이다. 0이 나올 때까지 반복하면 된다.
LCM: 두 수 a와 b를 받으면, a와 b를 곱한 값에서 GCD를 나눈 값이 LCM이다. ((a*b) / gcd)

 

import java.io.*;

public class LCM_1934 {
    
    // 유클리드 호제법으로 구하는 gcd, lcm
    
    // a와 b를 나눈 나머지가 0이 될 때 작은 수가 gcd이다
    public static int gcd(int a, int b) {
        while (b > 0) {
            int tmp = a;
            a = b;
            b = tmp % b;
        }
        return a;
    }
    
    // 유클리드 호제법으로 lcm을 구하려면 a, b를 곱한 값에서 gcd를 나누면 된다
    public static int lcm(int a, int b) {
        return a*b/gcd(a,b);
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        
        int T = stoi(br.readLine());
        
        int a, b;
        for (int i=0; i<T; i++) {
            String str = br.readLine();
            a = stoi(str.split(" ")[0]);
            b = stoi(str.split(" ")[1]);
            
            sb.append(lcm(a, b)).append("\n");
        }
        System.out.println(sb);
        
        br.close();
    }
    
    public static int stoi(String str) {
        return Integer.parseInt(str);
    }

}

 

로그인

 

 

작성일자: 2023-09-09