[ 백준 ] 1735번 - 분수 합

< 문제 정보 >

[ 문제 ]

자연수로 이뤄진 2개의 분수에 대하여 기약분수의 형태로 구하는 프로그램을 작성하시오

[ 예시 ]

• 입력 :
  2 7
  3 5
• 출력 :
  31 35

[ 규칙 ]

네 개의 자연수 <= 30,000

[ 백준 ]

• 유클리드 호제법
• 출처 : https://www.acmicpc.net/problem/1735

< 풀이 >

주어진 분수 간의 합을 먼저 구한 후, 구해진 분모와 분자의 최대공약수를 유클리드 알고리즘을
이용하여 구하고, 두 수 모두 나누면 기약 분수가 된다.

[ 코드 ]

import java.util.Scanner;
public class BaekJoon1735 {
    public static void main(String[] args) {
        int[] num = new int[4];
        int gcd;
        int deno, nume;
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < num.length; i++) {
            num[i] = sc.nextInt();
        }
        deno = num[0]*num[3]+num[2]*num[1];
        nume = num[1]*num[3];
        gcd = GCD(deno, nume);
        System.out.println(deno/gcd + " " + nume/gcd);
    }
    public static int GCD(int a, int b){
        if (a%b == 0)
            return b;
        else
            return GCD(b,a%b);
    }
}

유클리드 알고리즘에서 반복문과 재귀 함수 2가지 방법이 있다.
재귀 함수는 코드를 더욱 단순하게 만들지만, 피보나치 수열과 같은 경우에는 반복문보다 메모리를 많이 잡아 먹기에 주의해서 쓰자