백준 13241 최소공배수

문제

처음에는 1씩 더해서 해결하려 했지만, 시간초과가 발생했다.

수학적 지식이 있어야 풀 수 있는 문제였다. 

방법

유클리드 호제법을 사용하면 구하면 된다. 

먼저, 최대공약수를 구하고 

두 수의 곱 / 최대공약수를 하면 최소공배수가 되게 된다.

x * y / gcd 

 

예로 들면 두 수 28과 18이 있으면

28 % 18 = 10 

18 % 10 = 8

10 % 8 = 2

8 % 2 = 0 

최대공약수는 2이다. 

 

28과 18을 계속 나누는 과정을 좀 더 자세히 말해보면

큰 수 % 작은수 = 결과가 나오게 되는데, 결과가 0이 아니게 되면 

작은수와 결과를 다시 % 연산을 진행한다. 

계속해서 연산을 진행하다가 % 연산 시 0이 나오면 작은 수가 최대공약수(gcd)가 된다. 

코드

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

public class Main {
    // 13241
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        long x = Integer.parseInt(st.nextToken());
        long y = Integer.parseInt(st.nextToken());
        long bigNum = Math.max(x, y);
        long smallNum = Math.min(x, y);
        long gcd;

        while (true) {
            long tmp = bigNum % smallNum;
            if (tmp == 0) {
                gcd = smallNum;
                break;
            } else {
                bigNum = Math.max(smallNum, tmp);
                smallNum = Math.min(smallNum, tmp);
            }
        }
        long lcm = x * y / gcd;
        bw.write(String.valueOf(lcm));

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