[Java] 백준(브론즈-1) 2609번 - 최대공약수와 최소공배수

문제 풀이

---

이번 문제는 최대공약수를 구하는 것이 관건이다.
최대공약수를 구하는데 특정 수의 약수가 매우 많다면, 인수분해 및 두수를 비교하여 곱하는 과정에서 많은 시간이 소요된다.
그래서 유클리드 호제법을 활용하여 최대공약수를 구해야 한다.

유클리드 호제법을 활용한 풀이는 최대공약수와 최소공배수 문제에서 자세히 다루었으니 참고하자.

아이디어 도출

• 두 수를 입력받고 두 수 중 큰수와 작은수를 구분하여 최대공약수와 최소공배수를 구한다.
• 유클리드 호제법인 큰 수를 작은 수로나눈 나머지가 0보다 클 경우 재귀함수를 통해 0이 되는 시점의 작은 수을 반환하는 함수를 통해 최대공약수를 구한다.
• 두 수의 곱을 최대공약수로 나누어 최소공배수를 구한다.

최대공약수와 최소공배수는 많이 접하고 풀어봤던 문제이기에 솝쉽게 아이디어를 낼 수 있었다. 이제 코드를 작성해보자.

StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());

int bn = Math.max(N, M);
int sn = Math.min(N, M);

N과 M을 입력받고 큰 수 bn과 작은 수 sn을 정하여 저장한다.

int GCD = eucd(bn, sn); // 유클리드 호제법으로 최대공약수 구함
int LCM = N * M / GCD; // 최소공배수

bw.write(GCD+"\n"+LCM+"\n");    

eucd() 메서드에 큰 수와 작은 수를 인자로 넘겨 호출하고 해당 메서드로 구한 최대공약수를 가지고 최소공배수를 구하면 된다.

eucd 메서드를 살퍄보면 다음과 같다.

static int eucd(int bn, int sn) {
    int r = bn % sn;
    if(r == 0) return sn;
    else return eucd(sn, r);
}

bn을 sn으로 나눈 나머지를 r에 저장하는데 r이 0보다 클 경우 재귀함수를 통해 0이 되는 시점의 sn을 반환하게 되면 최대공약수를 구할 수 있다.

작성코드

---

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

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

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        int bn = Math.max(N, M);
        int sn = Math.min(N, M);

        int GCD = eucd(bn, sn); // 유클리드 호제법으로 최대공약수 구함
        int LCM = N * M / GCD; // 최소공배수
        
        bw.write(GCD+"\n"+LCM+"\n");    

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

    static int eucd(int bn, int sn) {
        int r = bn % sn;
        if(r == 0) return sn;
        else return eucd(sn, r);
    }
}

회고

• 최대공약수를 구하는 알고리즘인 유클리드 호제법을 활용할 수 있었다.

출처

• 해당 문제의 저작권은 문제를 만든이에게 있으며 자세한 내용은 문제 링크에서 참조바랍니다.