[Java] 백준알고리즘 #1735 분수 합

백준알고리즘 #1735 분수 합

두 분수를 합한 수를 약분하여 기약분수로 표시하는 문제.

 

두 분수를 합하는 방법은

2/7 + 3/5 의 경우

분모를 통일시켜줘야 하기 때문에 2/7 에 5를 곱하고, 3/5에 7을 곱해준다.

10/35 + 21/35

즉 31/35가 되는 것. 분자는 각 분모에 곱해진 수를 곱하여 더하고, 분모는 서로 곱하면 된다.

 

예를 하나 더 들어 보자면.

2/5 와 1/10의 경우, 각 수에 10과 5를 곱해주면

20/50 과 5/50 이 되어 25/50이 된다.

 

이를 기약분수로 나타내기 위해서는 분자와 분모의 최대공약수를 이용해 나눠주면 된다.

 

이는 앞서 사용했었던 유클리드 호제법을 이용해 최대공약수를 이용하면 간단하다.

2023.10.10 - [Java/백준알고리즘] - [Java] 백준알고리즘 #13241 최소공배수

[Java] 백준알고리즘 #13241 최소공배수

 

전체 코드는 다음과 같다.

import java.util.Scanner;

public class Main {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int a = sc.nextInt(); // 첫번째 줄 분자
        int b = sc.nextInt(); // 첫번째 줄 분모
        int c = sc.nextInt(); // 두번째 줄 분자
        int d = sc.nextInt(); // 두번째 줄 분모

        int e = a * d + b * c; // 약분 전의 분자 합
        int f = b * d; // 약분 전의 분모
        int gcd = 1;

        while (true) { // 유클리드 호제법
            int tmp = f % e;
            if (tmp == 0) {
                gcd = e;
                break;
            }
            f = e;
            e = tmp;
        }
        e = (a * d + b * c) / gcd;
        f = b * d / gcd;

        System.out.println(e + " " + f);
        sc.close();
    }
}