[ 백준 1735 / Java ] 분수 합

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

1735번: 분수 합

 

문제

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

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

입력

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

출력

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

예제 입력 1 복사

2 7
3 5

예제 출력 1 복사

31 35

풀이

유클리드 호제법을 통해 문제를 풀면 쉽다.

 

분수 계산은,

a/A + b/B = a x B + c x A / A * B

이다.

 

여기서 최종결과는 기약 분수여야 하므로 먼저 분수를 더해주고 최종 결과물에서 분자와 분모의 최대 공약수를 구한 뒤,

분자와 분모에 각각 나누어 주었다.

 

최대 공약수를 구하는 과정에서 유클리드 호제법을 사용하였다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
    static int a, A;
    static int b, B;
    // 분수 계산 방법
    // a/A + b/B = ((a*B)+(b*A))/(A*B)
    // 분수를 더하고 최대 공약수로 분자와 분모를 각각 나누어 준다.
    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());
        A = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        b = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        int numberator = (a*B)+(b*A);
        int denominator = A*B;
        int mod = gcd(numberator, denominator); 
        numberator /= mod;
        denominator /=mod;
        System.out.print(numberator + " " + denominator);
    }
    public static int gcd(int a, int b) {
        //a가 b보다 큰 경우에 대해서 유클리드 호제법 수행
        if(a <= b) {
            int temp = a; 
            a = b; 
            b = temp; 
        }
        if (b == 0) { 
            return a;
        }
        return gcd(b, a%b); 
    }
}