Baekjoon 문제 풀기 (2609번 : 최대공약수와 최소공배수) Java

2609번 : 최대공약수와 최소공배수

1. 문제읽기

---

유클리드 호제법을 이용한 문제

파이썬으로 풀어봤던 문제지만 유클리드 호제법은 까먹었다..^^..

2. 제출 코드

---

무식한 방법으로 풀긴 했는데 두 번의 반례를 못찾아서 백준 질문하기를 이용했다.
질문의 답에 있던 반례를 하나씩 넣어보니 정답이 아닌 것들이 있었다.. 역시 사람들은 다 비슷한가보다..

유클리드 호제법을 기억하진 못했지만 최대공약수로 나눈 나머지 수를 곱하고 거기에 최대공약수를 곱해주면 최소공배수라는 것은 기억해내서 그나마 풀 수 있었다.

1. num변수 초기화
   num 변수를 초기화를 시켜주지 않아서 반례 200 200일 때 40 1000이 나왔다. 원래 답은 200 200이다. a와 b가 둘다 5가 되면서 num이 6이 되고 while문을 빠져나가 버린다. 그래서 여기서 if문을 나올 때 num값을 초기화 시켜줘야 한다는 사실을 깨달았다.
2. 초기화를 2로?
   그래서 처음과 같이 초기화를 2로 해줬더니 20 20에서 10 40으로 출력이 되었다. 답은 20 20이다. 왜그런지 봤더니 초기화 후 num++코드가 바로 실행되면서 num이 2일 때 건너뛰어버리는 것이다. 그래서 num변수를 1로 초기화 시켜주었다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2609 {
    public static void main(String[] args) throws IOException {
        // 24 = 6*4
        // 18 = 6*3
        // 6, 6*12
        // n/최대공약수 끼리 곱하면 최소공배수 나옴
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();
        // 최대공약수 구하기
        int max = 1;
        int num = 2;
        while(Math.min(a,b)/(double)num >= 1) {
            if(a%num == 0 && b%num == 0) {
                max *= num;
                a /= num;
                b /= num;
                num = 1; // 초기화
            }
            num++;
        }
        sb.append(max).append("\n");
        sb.append(a*b*max);
        System.out.println(sb);
    }
}

3. 공부할 것

---

유클리드 호제법이라는 알고리즘이 굳이 필요할까? 싶었지만 프로젝트를 하면서 나도 모르게 배웠던 알고리즘을 썼던 기억이 떠올라서 그래도 알아둬야겠다 싶다.
기존 포스팅에서 java로만 코드를 바꿨다.

유클리드 호제법

최대공약수를 구하는 방법.
a를 b로 나눈 나머지를 r이라고 했을 때, a와 b의 최대공약수는 b와 r의 최대공약수이다.
단, a>b이다.

위 방법으로 b를 나머지를 0이 될때까지 계속 나눠서 최대공약수를 구할 수 있다.

최소공배수 구하기

최대공약수 : gcd = greatest common divisior
최소공배수 : lcm = least common multiple

a = gcd * x
b = gcd * y
(단, x, y는 서로소이다.)
a * b = gcd * gcd * x * y
lcm = gcd * x * y 이므로 lcm = a * b / gcd 가 도출된다.

정답 코드

a가 24이고 b가 18일 때, 유클리드 호제법을 적용하면 24와 18의 gcd는 18과 24%18의 gcd와 같다.
이걸 반복하면 아래와 같이 나타낼 수 있는데, 나머지가 0일 때 a값이 gcd가 된다.
gcd(24,18) -> gcd(18,24%18=6) = gcd(18,6) -> gcd(6, 18%6=0)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BOJ2609 {
    public static int gcd(int a, int b) {
        // 최대공약수 구하기
        while(b != 0) {  // b가 0일때까지
            int r = a%b;  // 나머지 r
            a = b;  // 값 바꿔주기
            b = r;
        }
        return a;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(bf.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        StringBuilder sb = new StringBuilder();

        sb.append(gcd(a,b)).append("\n");
        sb.append(a*b/gcd(a,b));
        System.out.println(sb);
    }
}