<Algorithm> 55. 1735번 분수 합(유클리드)

1. 1735번 분수 합

• 유클리드 호제법 문제

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br =new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int upA = Integer.parseInt(st.nextToken());
        int downA = Integer.parseInt(st.nextToken());
        
        st = new StringTokenizer(br.readLine());
        int upB = Integer.parseInt(st.nextToken());
        int downB = Integer.parseInt(st.nextToken());
        
        int quoA = gcm(downA, downB)/downA * upA;
        int quoB = gcm(downA, downB)/downB * upB;
        int sum = quoA + quoB;
        
        int gcdSum = 0;
        int gcm = gcm(downA, downB);
        
        while(gcdSum != 1) {
            gcdSum = gcd(sum, gcm);
            sum = sum / gcdSum;
            gcm = gcm / gcdSum;
        }// 기약분수 형태로 만들기
        System.out.println(sum+" "+gcm);
        
    }
    public static int gcd(int a, int b) {
        // 유클리드 호제법 이용, 최대 공약수 구하기
        if(a < b) {
            int temp = a;
            a = b;
            b = temp;
        }
        
        while(true) {
            int r = a % b;
            
            if(r == 0) {
                return b;
                // 0이면 b가 최대 공약수가 된다.
            }else {
                a = b;
                b = r;
                // a -> b, b -> r
            }            
        }
        
    }
    public static int gcm(int a, int b) {
        // 최소 공배수 = 두 수 곱 / 최대 공약수 
        return  (a * b) / gcd(a, b);
    }
    
}