[백준/1735번] 분수 합 (유클리드 호제법 응용)[Java]

문제

분수 A/B는 분자가 A, 분모가 B인 분수를 의미한다. A와 B는 모두 자연수라고 하자.

두 분수의 합 또한 분수로 표현할 수 있다. 두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오. 기약분수란 더 이상 약분되지 않는 분수를 의미한다.

입력

첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다.

출력

첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 빈 칸을 사이에 두고 순서대로 출력한다.

 

---

풀이

분수 1과 2를 입력받고 분모의 최소 공배수를 찾는다(유클리드 호제법(a*b/a와b의 최대공약수)).

그리고 분자에 분자*(분모/최대공약수)를 통해서 만약 2/7 과 3/5 라면  10/35와 21/35로 만들어준다.

 

여기서 주의할 점이 기약분수로 나타내야 하기 때문에 분자 분모를 두 수의 최대공약수로 나누어 주어야 기약분수로 나타낼 수 있다.ㅇㅅㅇ

 

 

import java.util.*;
import java.io.*;
import java.io.*;
 
public class Main {    
    public static void main(String[] args) throws IOException {
        BufferedReader br= new BufferedReader(new InputStreamReader(System.in));        
            
        StringTokenizer st= new StringTokenizer(br.readLine()); //첫번째 분수
        StringTokenizer st2= new StringTokenizer(br.readLine()); //두번째 분수
        
        int a= Integer.parseInt(st.nextToken()); // 1분자
        int b= Integer.parseInt(st.nextToken()); // 1 분모
        int a2= Integer.parseInt(st2.nextToken()); // 2분자
        int b2= Integer.parseInt(st2.nextToken()); // 2분모
        
        int temp =gb(b,b2); //분모 최소공배수 구하기
        int result =a*(temp/b)+a2*(temp/b2);
        
        System.out.println(result/gcd(temp,result)+" "+temp/gcd(temp,result));
        
        
    }
    public static int  gcd(int a, int b) {
        while(b!=0) {
            int r=a%b;
            a=b;
            b=r;
        }
        return a;
    }
    public static int gb(int a, int b) {
        return a*b/gcd(a,b);
    }
    
}

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

1735번: 분수 합