[Algorithm] 백준온라인저지 1934번(BOJ-1934) 최소공배수 Java로 문제풀이!! (수학)

---

안녕하세요 Coding-Knowjam입니다.

오늘은 백준 온라인 저지에 있는 1934번 최소공배수 문제를 풀어보겠습니다.

 

1. 문제 설명

설명에 앞서 아래 링크를 통해 문제를 읽고 오시길 바랍니다.

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

 

문제는 두 개의 수 사이의 최소공배수를 구하는 문제입니다.

최소공배수를 구하는 공식은 다음과 같이 표현할 수 있습니다.

최소공배수 = 두 개의 수 곱 / 최대공약수

왜 그런지는 소인수 분해를 해보시면 두 개의 수를 놓고 소인수 분해를 해보시면 쉽게 이해할 수 있습니다.

그렇다면 우리는 최대공약수를 구해야 합니다.

최대공약수를 구하는 알고리즘은 유클리드 호제법이 있습니다.

유클리드 호제법이 대해서는 제가 포스팅한 내용이 있으니 궁금하면 아래 링크를 통해 참고하시길 바랍니다.

[Algorithm] 유클리드 호제법을 Java로 구현해보자!! (with BOJ 2609)

 

2. Java로 문제 풀이

package study.blog.codingnojam.algorithm;

import java.io.*;

public class BOJ_1934 {

    // 백준온라인저지 1934번 최소공배수 Java로 문제풀이
    public static void main(String[] args) throws IOException {

        // 주어진 입력정보 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 테스트 케이스 갯수
        int T = Integer.parseInt(br.readLine());

        // 테스트 케이스 갯수만큼 반복
        for (int i = 0; i < T; i++) {
            // 두개의 수 받기
            String[] temp = br.readLine().split(" ");
            int A = Integer.parseInt(temp[0]);
            int B = Integer.parseInt(temp[1]);

            // 최대공약수 구하기
            int gcf = euclidean(Math.max(A, B), Math.min(A, B));

            // 최소공배수 = 두 수의 곱 / 최대공약수
            int lcm = A * B / gcf ;

            // 출력
            bw.write(String.valueOf(lcm));
            bw.newLine();
        }
        bw.flush();
    }

    /**
     * 유클리드 호제법을 구현한 메서드
     * @param bigNumber : 두개의 수 중 큰 수
     * @param smallNumber : 두개의 수 중 작은 수
     * @return
     * 큰 수를 작은 수로 나눈 나머지가 0이면 작은 수를 리턴
     * 0이 아니면 재귀형태로 다시 메서드 호출하며 파라미터로 작은 수, 나머지를 넘거줌
     */
    static int euclidean(int bigNumber, int smallNumber) {
        // 큰 수를 작은 수로 나눈 나머지를 구함
        int R = bigNumber % smallNumber;
        // 나머지가 0인 경우 작은 수 리턴
        if (R == 0) {
            return smallNumber;
        } else {
            // 나머지가 0이 아닌경우 재귀형태로 자기 자신 호출
            // 파라미터로 작은 수, 나머지를 넘김
            return euclidean(smallNumber, R);
        }
    }
}

 

작성한 코드 라인마다 주석을 달아놓았으니 천천히 읽어보시길 바랍니다.

유클리드 호제법을 구현할 줄만 알면 나머지는 문제에서 주어진대로 출력만 하면 되니 어렵지 않게 풀 수 있을 겁니다.

감사합니다.

---