백준 2436 (공약수) - java

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

2436번: 공약수

문제

어떤 두 자연수에 공통인 약수들 중에서 가장 큰 수를 최대공약수라고 하고, 두 자연수의 공통인 배수들 중에서 가장 작은 수를 최소공배수라고 한다.

예를 들어, 두 자연수 12와 90의 최대공약수는 6이며, 최소공배수는 180이다.

이와 반대로 두 개의 자연수 A, B가 주어졌을 때, A를 최대공약수로, B를 최소공배수로 하는 두 개의 자연수를 구할 수 있다. 그러나, 이러한 두 개의 자연수 쌍은 여러 개 있을 수 있으며, 또한 없을 수도 있다. 

예를 들어, 최대공약수가 6이며 최소공배수가 180인 두 정수는 위의 예에서와 같이 12와 90일 수도 있으며, 30과 36, 18과 60, 혹은 6과 180일 수도 있다. 그러나, 최대공약수가 6이며 최소공배수가 20인 두 자연수는 있을 수 없다.

두 개의 자연수가 주어졌을 때, 이 두 수를 최대공약수와 최소공배수로 하는 두 개의 자연수를 구하는 프로그램을 작성하시오. 

 

유형 : 유클리드 호제법

 

접근

• 가장 중요한 접근은 최대 공약수와 최소 공배수를 이용하는 것이다.
  • 두 자연수를 최대 공약수로 나눈다면 두 수는 서로소여야 한다 ! (약수가 1말고 존재하면 안되기 때문 !)
  • 그렇다면 최대 공약수로 나눈 두수의 최소 공배수는 ? : 최소 공배수 / 최대 공약수이다.
• tmpMax = 최소 공배수 / 최대 공약수라 하자
  • tmpMax의 약수를 찾음과 동시에 두 수가 서로소 (유클리드 호제법의 결과가 1)인지 확인하자 !
  • 여러개 일 경우 sum값을 비교하자

전체 코드

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

public class Main {
    static int a = 0;
    static int b = 0;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        a = Integer.parseInt(st.nextToken());
        b = Integer.parseInt(st.nextToken());

        if(a == b){
            System.out.println(a +" "+ b);
            return;
        }

        int tmpMax = b / a;

        int sum = b;
        int min = 0;
        int max = 0;

        for(int i=1;i<=Math.sqrt(tmpMax);i++){

            if(tmpMax % i == 0){
                int f = i;
                int s = tmpMax / i;

                if(find(f,s) ==1){
                    if(f + s <= sum){
                        sum = f + s;
                        min = f;
                        max = s;
                    }
                }
            }

        }

        System.out.println((a*Math.min(min,max))+" "+(a*Math.max(min,max)));
        br.close();
    }

    static int find(int f,int s){
        if(s == 0)
            return f;

        return find(s,f % s);
    }
}