[java] 백준 1735 분수 합

분수의 합을 기약분수로 구하는 문제이다.

 

기약분수란 더 이상 약분이 되지 않는 분수를 의미한다.

 

그렇다면 기약분수는 어떻게 구하는 것일까?

 

각 수가 더 이상 나누어지지 않기 위해서는 통분한 후 최대공약수로 나누면 해결된다.

 

최대공약수를 구하는 공식은 아래 글에 정리되어 있다.

 

 

https://miacoder.tistory.com/42

[java] 백준 13241 최소공배수 자바

 

 

예를 들어보자 6/10 과  5/15가 있다. 여기서 각 값을 통분한다. 그렇다면 90/150, 50/150이 된다.

 

두 값을 더하면 140/150이 된다. 140과 150의 최대공약수를 구하면 10이다.

 

140과 150을 각각 10으로 나누면 기약분수 형태인 14/15가 되는것을 확인 할 수 있다.

 

이 부분을 코드로 작성해 보자.

 

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

public class Main {
    public static void main(String[] args) throws Exception {

        Scanner sc = new Scanner(System.in);

        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();

        int son = b * c + a * d;
       	// 더해서 통분한 분자 값
        int mom = b * d;
		// 통분한 분모 값
        
        int gdc = gdc(son, mom);
        //최대공약수 구하기

        System.out.print((son / gdc) + " " + (mom / gdc));
		// 더해서 통분한 분자, 분모 값을 최대공약수로 나눈 기약분수 값을 출력함.
        sc.close();
        
    }

    public static int gdc(int a, int b) {
    	//유클리드 호제법을 활용한 최대공약수 구하는 메소드
        
        int r = a % b;

        if (r == 0) {
            return b;
        }

        else {
            return gdc(b, r);
        }
    }

}