1943 최소공배수 JAVA

이 문제는 내가 작성한 최소 공배수와 최대 공약수 문제 풀이를 읽었다면 그냥 똑같기 때문에 매우 쉽게 구현할 수 있다.

 

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

 

워낙 쉬운 문제이기에, 따로 설명은 안하지만 의외로 시간초과가 많았던 거 같다.

이 문제를 풀 때, 혹시나 순회하면서 나머지를 구하는 방식은 잘못하면 시간 초과가 날 수 있다는 것을 유념하면 된다.

이전에도 말했던 유클리드 호재법을 이용해서 풀면 너무나 쉽기 때문에 한번 보는 걸 추천한다.

 

import java.io.*;
import java.util.StringTokenizer;

public class M1934 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        int T = Integer.parseInt(br.readLine());
        int grtDvd = 0;

        while(T --> 0) {
            StringTokenizer st = new StringTokenizer(br.readLine(), " ");
            int num1 = Integer.parseInt(st.nextToken());
            int num2 = Integer.parseInt(st.nextToken());

            sb.append(num1 * num2 / calculateGrtDvd(num1, num2))
              .append("\n");
        }
        System.out.println(sb);
    }

    private static int calculateGrtDvd(int num1, int num2) {
        if(num2 == 0) return num1;

        return calculateGrtDvd(num2, num1%num2);
    }
}