[또 LIE ?] 5주차 결과

 문제

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

13241번: 최소공배수

코드

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

public class TheLeastCommonMultiple {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] s = br.readLine().split(" ");
        long a = Long.parseLong(s[0]); // 작은 수
        long b = Long.parseLong(s[1]); // 큰 수
        long save = a*b; // 최소공배수의 기본인 두 수의 곱에서 찾기위해 먼저 두 수를 곱해줌.

        long result;
        while (true) { // 최대공약수를 구하는 방법을 이용해 최소공배수를 구함.
            result = b % a;

            b = a;
            a = result;

            if (result == 0) { // 두 수가 맞아떨어지거나 b보다 a가 더 커지면 종료.
                break;
            }
        }

        bw.write((save / b) + "\n");

        bw.flush();
        br.close();
        bw.close();
    }

}

 풀이

└ 유클리드 호제법은 최대공약수를 최적의 시간복잡도를 이용하여 구하는 것이다. 이 최대공약수를 활용해 최소공배수도 쉽게 구할 수 있다.

 느낀점

└최대공약수를 구한다는 코드는 처음 짜봤는데, 유클리드 호제법이라는 알고리즘을 익히고 다른 많은 문제를 풀 수 있었다.