백준 1934번 : 최소공배수

---

이번 문제는 두 숫자 A와 B를 입력 받고 이 두 숫자의 최소공배수를 구하는 문제이다.

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

public class Main {
    public static void main(String[] args) throws java.io.IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());

            System.out.println((x * y) / gcd(x, y));
        }
    }
    public static int gcd(int x, int y) {
        while (y != 0) {
            int temp = y;
            y = x % y;
            x = temp;
        }
        return x;
    }
}

사실 이 문제는 유클리드 호제법과 해당 호제법 사용 후 최소공배수를 구하는 방식만 알고 있다면 풀 수 있는 문제이다.
다만, 이 공식을 알고있지 않다면 생각보다 복잡하고 어려울 것이다.

유클리드 호제법에 관련된 내용은 위키백과에 있다.
이 내용이 어렵다면 블로그를 참조해도 된다.

이 유클리드 호제법은 기본적으로 자연수의 최대공약수를 구하는 알고리즘이다.
현재 소스 코드 중 gcd 함수가 유클리드 호제법을 활용하고 있으며 진행은 다음과 같다.

1. 자연수 x, y (x > y) 입력
2. y가 0이라면 x를 출력하고 알고리즘을 종료
3. x가 y로 나누어 떨어지면, y를 출력하고 알고리즘 종료
4. 그렇지 않다면, x를 y로 나눈 나머지를 새롭게 x에 대입하고 x와 y를 바꾼 뒤 3번으로 돌아감

마지막으로 초기에 입력 받은 두 자연수 x와 y를 곱하고 최대공약수로 나누면 최소공배수를 알 수 있다.

물론 현재는 while문을 사용하여 공식을 살짝 풀어썼지만, 최대한 유클리드 호제법 공식과 비슷하게 재귀함수를 사용할 수도 있다.

public static int gcd(int x, int y) {
    if (y == 0)
        return x;
    return gcd(y, x%y);
    }

유클리드 호제법 함수인 gcd를 재귀함수로 표현한다면 위와 같다.

---

이번 문제부터 약수,소수,배수 파트이기 때문에 난이도가 낮아졌지만 수학적인 문제이기 때문에 공식을 모르면 헤맬 가능성이 있다.

참고로 다음 문제는 동일한데 단순히 입력 받는 개수가 없어서 현재 소스 코드의 for문만 삭제한 것이라 따로 업로드 하진 않는다.